下面是我自己的解答

#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#define MAX_LEN 128

bool match(char *S,char *P)
{
	bool F[MAX_LEN][MAX_LEN];

	int lenS = strlen(S);
	int lenP = strlen(P);

	for (int i = 0; i<MAX_LEN; i++)
	{
		for (int j = 0; j<MAX_LEN; j++)
		{
			F[i][j] = false;
		}
	}

	F[0][0] = true;


	for (int i = 1; i <=lenP; i++)
	{
		for (int j = 1; j<=lenS; j++)
		{
			if (F[i-1][j-1])
			{
				if (S[j-1] == P[i-1] || P[i-1] == '?' || P[i-1] == '*')
				{
					F[i][j] = true;
					continue;
				}
			}

			if (F[i-1][j])
			{
				if (P[i-1] == '*')
				{
					F[i][j] = true;
					continue;
				}

			}

			if (F[i][j-1])
			{
				if (P[i-1] == '*')
				{
					F[i][j] = true;
					continue;
				}
			}
		}
	}
	return F[lenP][lenS];
}




int _tmain(int argc,_TCHAR* argv[])
{
	char *S = "CISCO";
	char *P = "*C?";

	bool isMatch = match(S,P);

	if (isMatch)
	{
		printf("Match\n");
	}
	else
	{
		printf("No Match\n");
	}
	return 0;
}
网上有一个更详细的解答：

网上有一个更详细的描述

参考：http://blog.csdn.net/lifajun90/article/details/10582733

解法一：

由于以前做过一个类似的题目http://soj.me/1197,所以我的第一印象就是用动态规划，具体思路如下：

用dp[i][j]表示字符串s的前i个字符和字符串p的前j个字符是否匹配，那么状态转移情况如下：

if (dp[i-1][j-1] && (s[i] == p[j] || '?' == p[j])) dp[i][j] = true,即如果前i-1和前j-1个字符匹配，当前字符也匹配，那么前i个和前j个也匹配。

如果p的当前字符为'*'号，那么可以分两种情况：

(1) 如果dp[i-1][j-1]，那么p的前j个字符和s的前k(i-1<=k<=len_s)个字符都匹配，注意这里有一个i-1，因为*可以匹配空串。

(2)如果dp[i][j-1]，即s的前i个字符和字符串p的前j-1个字符，那么p的前j个字符和s的前k(i<=k<=len_s)个字符匹配，注意这里没有i-1，因为这是让*去匹配i后面的字符串。

这种解法的时间复杂度和空间复杂度都为O(N^2)，所以在leetcode上只能过小数据不能过大数据。

具体实现代码如下：

解法二(递归解法)：

解法一不能过大数据的原因在于两层for循环其实执行了多余的匹配过程，其实对于这种匹配来说如果*s和*p相等的话我们可以直接把指针往后移动，从而把数据规模缩小。这种做法的难点同样在对*号的处理上，因为*号可以匹配多个字符，所以在递归解法中需要回溯。

因为递归和回溯的代价都太高，所以该解法也只能过小数据，不能过大数据。

具体代码实现如下：

copy