题目
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
思路
分为三种情况：
- 单独的“.”：直接跳过一个字符
- 单独的“*”：依次去掉若干相同的字符，判断后面是否匹配
- “.*”一起：依次去掉若干字符，判断后面是否匹配
在后两种情况下可以采用递归简化代码。
实现一
class Solution {
public:
bool isMatch(string s, string p) {
int i=0, j=0;
while(i<p.size()){
if(i+1<p.size() && p[i+1]=='*'){
if(p[i]=='.'){
for(int m=j; m<=s.size(); m++){
if(isMatch(s.substr(m,s.size()-m),p.substr(i+2,p.size()-i-2)))
return true;
}
}
else{
for(int m=j; m<=s.size() && ((m==j)||(s[m-1]==p[i])); m++){
if(isMatch(s.substr(m,s.size()-m),p.substr(i+2,p.size()-i-2)))
return true;
}
}
return false;
}
else if(p[i]=='.'){
i++; j++;
}
else{
if(s[j]==p[i]){
i++; j++;
}
else{
return false;
}
}
}
return i==p.size()&&j==s.size();
}
};
思考一
为了快速实现功能，代码写得巨丑无比。而且递归真的很慢，估计时间复杂度可能达到指数水平，运行时间排在后三分之一左右。粗略看了排名靠前的代码，使用了动态规划。所以现在想想怎么把递归转换成动态规划。可以达到O(nm)的时间复杂度。
- 首先考虑将递归转化为记忆化搜索。用二维数组d[a][b]表示s.substr(a,s.size()-a)与p.substr(b,p.size()-b)是否匹配。这就避免了递归。
- 再考虑将记忆化搜索转化成动态规划，关键在于推导其递推关系。
数组要使用的大小为dp[s.size()+1][p.size()+1]。
考虑初始条件。一开始打算使用dp[s.size()][p.size()]代表两个空串的关系，自然是相等的，为true。另外当p的子串中没有“*”时，长度不等的子串必然不等，所以数组的大部分空间内必然都是false。所以可以考虑现将数组初始化为false，再将dp[s.size()][p.size()]置为true。但实际操作中发现这样从后往前会带来一些问题，所以后来使用dp[0][0]代表两个空串的关系，置为true。中间的递推公式搞了半天，不过看着答案边想边写总算弄出来了。
实现二
class Solution {
public:
bool isMatch(string s, string p) {
vector<vector<bool>> dp(s.size()+1, vector<bool>(p.size()+1, false));
dp[0][0] = true;
for(int i=0; i<=s.size(); i++){
for(int j=1; j<=p.size(); j++){
if(p[j-1]=='*'){
dp[i][j] = dp[i][j-2] || (i>0 && (s[i-1]==p[j-2] || p[j-2]=='.') && dp[i-1][j]);
}
else{
dp[i][j] = i>0 && dp[i-1][j-1] && (p[j-1]=='.' || s[i-1]==p[j-1]);
}
}
}
return dp[s.size()][p.size()];
}
};
思考二
用上面的方法达到了前三分之一的水平。再看题解，发现还有O(n)的解法，大惊失色。
看了下，和我之前写的方法一差不多，感觉这题解的时间复杂度估计有问题。所以懒得写了，复制下来直接提交，结果发现在后40%左右，和我一开始想出来的方法差不多。看来递归还是慢啊……
