1.正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
分析 dp[i][j] 表示s的前i个字符和p前j个字符是否匹配。则
if (p[j-1] == s[i-1] || p[j-1] == '.') dp[i][j] = dp[i-1][j-1];
如果 p[j - 1] == '*':
如果 p[j-2] == s[i-1] || p[j-2] == '.'
dp[i][j] = dp[i][j-2] || dp[i-1][j];
否则
dp[i][j] = dp[i][j-2];
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
dp[0][0] = 1;
for(int i = 1; i <= n; i++)
if(p[i-1] == '*' && dp[0][i-2])
dp[0][i] = 1;
for(int i = 1; i <= m; i++)
dp[i][0] = 0;
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= n; ++j) {
if(p[j-1] == s[i-1] || p[j-1] == '.')
dp[i][j] = dp[i-1][j-1];
else if(p[j-1] == '*') {
if(p[j-2] == s[i-1] || p[j-2] == '.')
dp[i][j] = dp[i][j-2] || dp[i-1][j];
else dp[i][j] = dp[i][j-2];
}
}
}
return dp[m][n];
}
2.通配符匹配
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ’?’ 和 ’*‘ 的通配符匹配。
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
说明:
- s 可能为空，且只包含从 a-z 的小写字母。
- p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
int dp[m+1][n+1];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1; //two empty str matches
for (int i = 0; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p[j - 1] == '*') {
dp[i][j] = dp[i][j - 1] || (i && dp[i - 1][j]);
}else{
dp[i][j] = i && dp[i - 1][j - 1] && (s[i-1] == p[j - 1] || p[j - 1] == '?');
}
}
}
return dp[m][n];
}
