LeeTCode(动态规划)——Wildcard Matching 外卡匹配

Given an input string (s) and a pattern §, implement wildcard pattern matching with support for ‘?’ and ‘*’.

‘?’ Matches any single character.
‘*’ Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like ? or *.

题目大意：

给定源字符串和模式字符串，看是否相等。模式字符串中有两个特殊字符：
*：可以替代0或n个字符
?：可以替代1个字符

题目解析：

使用动态规划的思想做，建立一个m*n的表，填表，参见：
http://www.cnblogs.com/grandyang/p/4401196.html

具体代码：

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 500
bool dp[MAXN][MAXN];//dp[i][j]表示源字符串s的前i个字符是否能与模式字符串的前j个相匹配
bool isMatched(string s,string p) {
	fill(dp[0],dp[0]+MAXN*MAXN,false);
	int len_s=s.size(),len_p=p.size();
	dp[0][0]=true;
	for(int i=1; i<=len_p; i++) {
		if(p[i-1]=='*') dp[0][i]=dp[0][i-1];
	}
	for(int i=1; i<=len_s; i++)
		for(int j=1; j<=len_p; j++) {
			if(p[j-1]=='*') {
				dp[i][j]=dp[i-1][j]||dp[i][j-1];
			}else{
				dp[i][j]=(s[i-1]==p[j-1]||p[j-1]=='?')&&dp[i-1][j-1];				
			}
		}
	return dp[len_s][len_p];
}
int main() {
	string s,p;
	while(cin>>s>>p) {
		if(isMatched(s,p))
			cout<<"Yes"<<endl;
		else
			cout<<"No"<<endl;
	}
	return 0;
}