一開始採用递归写。TLE。

class Solution {public:	bool flag;	int n,m;	void dfs(int id0,const char *s,int id1,const char *p){		if(flag)return;		if(id0>=n){			if(id1>=m)flag=1;			else{				int j=0;				while(j
     
      =m)flag=1;			}			return;		}		else if(id1>=m)return;		if(p[id1]=='?
     

'||p[id1]==s[id0]){ dfs(id0+1,s,id1+1,p); } else if(p[id1]=='*'){ for(int j=id0;j<n;++j) dfs(j,s,id1+1,p); } } bool isMatch(const char *s, const char *p) { for(n=0;s[n];++n); for(m=0;p[m];++m); flag=0; dfs(0,s,0,p); return flag; } };

粗剪枝了，还是超时。

看了下Discuss，发现能够贪心：

class Solution {public:	bool isMatch(const char *s, const char *p) {		const char*lastp=NULL,*lasts=NULL;		while(*s){			if(*s==*p||*p=='?'){				p++;				s++;			}			else if(*p=='*'){				//不匹配，仅仅记录				lastp=p++;				lasts=s;			}			else if(lastp!=NULL){				p=lastp+1;				s=++lasts;//逐渐递增匹配1个字符、2个字符...			}			else return false;		}		while(*p&&*p=='*')p++;		return *p=='\0';	}};

採用DP：

用dp[i,j]表示s[0,..,i]与p[0,..,j]是否匹配

dp[i,j]=1 if (p[j]=='*'&&(dp[i-1,j]||dp[i][j-1]||dp[i-1][j-1]))

dp[i,j]=1 if ((p[j]=='?'||s[i]==p[j]])&&dp[i-1][j-1])

时间复杂度O(nm)，能够採用滚动数组，否则会超内存。空间复杂度O(m)

可是，会超时

bool isMatch(const char *s, const char *p) {		int n=strlen(s),m=strlen(p),i,j;		bool **dp=new bool*[2];		for(i=0;i<2;++i){			dp[i]=new bool[m+1];			memset(dp[i],0,sizeof(bool)*(m+1));		}		dp[0][0]=1;		bool flag=0;		for(i=1;i<=n;++i){			for(j=1;j<=m;++j){				if(dp[flag][j-1]&&(p[j-1]=='?'||s[i-1]==p[j-1]))					dp[1-flag][j]=1;				else if(p[j-1]=='*'&&(dp[flag][j-1]||dp[flag][j]||dp[1-flag][j-1]))					dp[1-flag][j]=1;			}			flag=1-flag;		}		bool ans=dp[1][m];		for(i=0;i<2;++i)delete[] dp[i];		delete[]dp;		return ans;	}