下面是我自己的解答

#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;
}
网上有一个更详细的解答：@H_301_3@ 

 

 
 
网上有一个更详细的描述
 
参考：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上只能过小数据不能过大数据。
 
 具体实现代码如下：
 
 
 
 
 
 
  
 
   [cpp] 
   view plain 
   copy 
   
 
   
 
  
 
 
 
 
 
  
 //dp解法
 
  
 constintN=105;
 
  
 booldp[N][N];
 
  
 
 
  
 classSolution{
 
  
public:
 
  
boolisMatch(char*s,char*p){
 
  
 //StarttypingyourC/C++solutionbelow
 
  
//DONOTwriteintmain()function
 
  
if(*s=='\0'){
 
  
while(*p=='*')p++;
 
  
return*p=='\0';
 
  
 }
 
  
if(*p=='\0')returnfalse;
 
  
 
 
  
 memset(dp,false,153); background-color:inherit; font-weight:bold">sizeofdp);
 
  
 dp[0][0]=true;
 
  
 intlen_s=strlen(s),len_p=strlen(p);
 
  
for(intj=1;j<=len_p;j++){
 
  
inti=1;i<=len_s;i++){
 
  
if(dp[i-1][j-1]&&(s[i-1]==p[j-1]||'?'==p[j-1]))dp[i][j]=if('*'==p[j-1]){
 
  
if(dp[i-1][j-1]){
 
  
intk=i-1;k<=len_s;k++)dp[k][j]=true;
 
  
break;
 
  
 }elseif(dp[i][j-1]){
 
  
intk=i;k<=len_s;k++)dp[k][j]=break;
 
  
 }
 
  
returndp[len_s][len_p];
 
  
 };
 
 
 
 

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