来源：Leetcode
原帖：http://oj.leetcode.com/problems/regular-expression-matching/
题目：
Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "a*") ? true
isMatch("aa", ".*") ? true
isMatch("ab", ".*") ? true
isMatch("aab", "c*a*b") ? true zero or more
思路：
http://www.cnblogs.com/zuoyuan/p/3781773.html
解题思路：正则表达式匹配的判断。网上很多的解法是用递归做的，用java和c++都可以过，但同样用python就TLE，说明这道题其实考察的不是递归。而是动态规划，使用动态规划就可以AC了。这里的'*'号表示重复前面的字符，注意是可以重复0次的。
先来看递归的解法：
如果P[j+1]!='*'，S[i] == P[j]=>匹配下一位(i+1, j+1)，S[i]!=P[j]=>匹配失败；
如果P[j+1]=='*'，S[i]==P[j]=>匹配下一位(i+1, j)或者(i, j+2)，S[i]!=P[j]=>匹配下一位(i,j+2)。
匹配成功的条件为S[i]=='\0' && P[j]=='\0'。
代码：
原帖：http://oj.leetcode.com/problems/regular-expression-matching/
题目：
Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "a*") ? true
isMatch("aa", ".*") ? true
isMatch("ab", ".*") ? true
isMatch("aab", "c*a*b") ? true zero or more
思路：
http://www.cnblogs.com/zuoyuan/p/3781773.html
解题思路：正则表达式匹配的判断。网上很多的解法是用递归做的，用java和c++都可以过，但同样用python就TLE，说明这道题其实考察的不是递归。而是动态规划，使用动态规划就可以AC了。这里的'*'号表示重复前面的字符，注意是可以重复0次的。
先来看递归的解法：
如果P[j+1]!='*'，S[i] == P[j]=>匹配下一位(i+1, j+1)，S[i]!=P[j]=>匹配失败；
如果P[j+1]=='*'，S[i]==P[j]=>匹配下一位(i+1, j)或者(i, j+2)，S[i]!=P[j]=>匹配下一位(i,j+2)。
匹配成功的条件为S[i]=='\0' && P[j]=='\0'。
代码：
class Solution {
public:
bool isMatch(const char *s, const char *p) {
if (*p == '\0') return *s == '\0';
if (*(p+1) == '*') {
if (isMatch(s, p+2)) return true; // match 0
while (*s && (*s == *p || *p == '.')) { // match 1,2,...
if (isMatch(s+1, p+2)) return true;
s++;
}
} else if (*s && (*p == *s || *p == '.') && isMatch(s+1, p+1)) // always check *s
return true;
return false;
}
};
// dp solution
class Solution {
public:
bool isMatch(const char* s, const char* p) {
if (*p == '\0') return *s == '\0';
int M = strlen(s), N = strlen(p);
vector<vector<bool> > dp(M+1, vector<bool>(N+1, false)); // 前i个字符in s和前j个字符in p的匹配
dp[0][0] = true;
for (int j = 0; j < N; ++j)
dp[0][j+1] = p[j] == '*' ? (j >= 1 && dp[0][j-1]) : false;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (s[i] == p[j] || p[j] == '.') {
dp[i+1][j+1] = dp[i][j];
} else if (p[j] == '*') {
dp[i+1][j+1] = dp[i+1][j-1] || ((s[i] == p[j-1] || p[j-1] == '.') && dp[i][j+1]);
}
}
}
return dp[M][N];
}
};
