解题思路
- 状态表示:所有满足s[1~i] 与p[1~j]匹配的集合
- 状态属性:集合是否为空
- 状态计算
- 如果p[j] 不是”_*” 那么当前字符必须匹配s[i] == p[j]或者p[j] == ‘.’可以匹配任意字符,且前面字符都匹配f[i-1][j-1]
- 如果p[j] 是 “_*” 划分集合
- 匹配0个: 因为p[j] = “_*” 那么匹配0个就代表当前字符没有匹配只有前面的字符匹配f[i][j-2]
- 匹配1个: 前面字符匹配f[i-1][j-2] 当前字符匹配一个s[i] = p[j-1]; 因为p[j] == ‘*’
- 匹配2个: 前面字符匹配f[i-2][j-2] 当前字符匹配s[i] = p[j-1] && s[i-1] = p[j-1];
- 匹配3个: 前面字符匹配f[i-3][j-2] 当前字符匹配s[i] = p[j-1] && s[i-1] = p[j-1] && s[i-2] = p[j-1];
- .......
- f[i][j] 是所有情况或起来,只要情况非空,就非空
- f[i][j] = f[i][j-2] || f[i-1][j-2] &&(s[i] = p[j-1]) || f[i-2][j-2] &&(s[i] = p[j-1])&&(s[i-1] = p[j-1]);
-
优化
- f[i-1][j] = f[i-1][j-2] || f[i-2][j-2] &&(s[i-1] = p[j-1]);
- 原状态转移都比现在的变形从第二项开始每一项都多了一个s[i] = p[j-1]
-
最终 f[i][j] = f[i][j-2] || f[i-1][j] &&(s[i] = p[j-1] || p[j-1] = ‘.’)
- 边界:第一个串为空,第二个串有可能匹配
- 第二个串为空,第一个串不可能匹配
*
class Solution {
public:
bool isMatch(string s, string p) {
int n = s.size();
int m = p.size();
s = ' ' +s;
p = ' ' +p;
vector<vector<bool>> f(n+1,vector<bool>(m+1,false));
f[0][0] = true;
for(int i=0;i<=n;++i)
for(int j=1;j<=m;++j)
{
//把_*看成一个整体,如果_后面有*,那么跳过这个字符
if( j+1 < p.size() && p[j+1] == '*') continue;
if(i && p[j] != '*')
{
f[i][j] = f[i-1][j-1] && (s[i] = p[j] || p[j] == '.');
}
else if(p[j] == '*')
{
f[i][j] = f[i][j-2] || i && f[i-1][j] &&(s[i] == p[j-1] || p[j-1] == '.');
}
}
return f[n][m];
}
};
6
赞!
赞!