问题来源
递归方法
class Solution {
public:
bool isMatch(string s, string p) {
if(p.size() == 0) return s.size() == 0;
bool first_match = (s[0] == p[0] or p[0]=='.');
if(p[1]=='*') return isMatch(s, p.substr(2, p.size()-2)) or (first_match and s.size() > 0 and isMatch(s.substr(1, s.size()-1), p));
else return first_match and s.size() > 0 and isMatch(s.substr(1, s.size()-1), p.substr(1, p.size()-1));
}
};
复杂度分析
令和
分别表示匹配串的长度和模式串的长度。
在最坏情况下，调用match(text[i:], pattern[2j:]的次数最多会达到(组合数)次。参考代码，i和j每次前进一步，均需要调用一次match。而到达
text[i:], pattern[2j:]一共存在种可能性，最坏情况下每种情况均需要调用
match(text[i:], pattern[2j:]。
改进思路
递归方法速度较慢的核心问题是存在重复调用的问题，如果我们记录下每次调用的结果，就可以将递归转换为动态规划。
动态规划解法
自顶向下（递归）
class Solution {
public:
bool dp(int i, int j, int* memo, string s, string p)
{
if(memo[j + i*(p.size()+1)] != -1)
{
return memo[j + i*(p.size()+1)];
}
else
{
if(j == p.size())
{
if(i == s.size())
{
memo[j + i*(p.size()+1)] = 1;
return 1;
}
else
{
memo[j + i*(p.size()+1)] = 0;
return 0;
}
}
bool first_match = (i < s.size() and (s[i] == p[j] or p[j] == '.'));
if(p[j+1] == '*')
{
bool result = dp(i, j+2, memo, s, p) or (first_match and dp(i+1, j, memo, s, p));
memo[j + i*(p.size()+1)] = result;
return result;
}
else
{
bool result = (first_match and dp(i + 1, j + 1, memo, s, p));
memo[j + i * (p.size() + 1)] = result;
return result;
}
}
}
bool isMatch(string s, string p)
{
int memo[(s.size() + 1)*(p.size() + 1)];
for(int i=0;i < (s.size() + 1)*(p.size() + 1);i++) memo[i]=-1;
bool result = dp(0, 0, memo, s, p);
return result;
}
};
自底向上（迭代，尾递归转迭代）
class Solution {
public:
bool isMatch(string s, string p)
{
int dp[(s.size() + 1)*(p.size() + 1)];
for(int i=0;i < (s.size() + 1)*(p.size() + 1);i++) dp[i]=0;
dp[(s.size() + 1)*(p.size() + 1)-1] = 1;
for(int i = s.size();i>=0;i--){
for(int j = p.size() - 1;j>=0;j--)
{
bool first_match = i < s.size() and (s[i] == p[j] or p[j] == '.');
if(p[j + 1] == '*')
{
dp[j + i * (p.size() + 1)] = dp[j + 2 + i * (p.size() + 1)] or (first_match and dp[j + (i + 1) * (p.size() + 1)]);
}
else
{
dp[j + i * (p.size() + 1)] = (first_match and dp[j + 1 + (i + 1) * (p.size() + 1)]);
}
}
}
return dp[0];
}
};
复杂度分析
最多计算dp的容量大小T*P次， 故时间复杂度
