算法
(动态规划) $O(nm)$
状态表示：f[i][j]表示p从j开始到结尾，是否能匹配s从i开始到结尾
状态转移：
- 如果p[j+1]不是通配符
'*'，则f[i][j]是真，当且仅当s[i]可以和p[j]匹配，且f[i+1][j+1]是真； - 如果p[j+1]是通配符
'*'，则下面的情况只要有一种满足，f[i][j]就是真；- f[i][j+2]是真；
- s[i]可以和p[j]匹配，且f[i+1][j]是真；
第1种情况下的状态转移很好理解，那第2种情况下的状态转移怎么理解呢？
最直观的转移方式是这样的：枚举通配符
'*'可以匹配多少个p[j]，只要有一种情况可以匹配，则f[i][j]就是真；
这样做的话，我们发现，f[i][j]除了枚举0个p[j]之外，其余的枚举操作都包含在f[i+1][j]中了，所以我们只需判断
f[i+1][j]是否为真，以及s[i]是否可以和p[j]匹配即可。
时间复杂度分析：$n$ 表示s的长度，$m$ 表示p的长度，总共 $nm$ 个状态，状态转移复杂度 $O(1)$，所以总时间复杂度是 $O(nm)$.
C++ 代码
class Solution {
public:
vector<vector<int>>f;
int n, m;
bool isMatch(string s, string p) {
n = s.size();
m = p.size();
f = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));
return dp(0, 0, s, p);
}
bool dp(int x, int y, string &s, string &p)
{
if (f[x][y] != -1) return f[x][y];
if (y == m)
return f[x][y] = x == n;
bool first_match = x < n && (s[x] == p[y] || p[y] == '.');
bool ans;
if (y + 1 < m && p[y + 1] == '*')
{
ans = dp(x, y + 2, s, p) || first_match && dp(x + 1, y, s, p);
}
else
ans = first_match && dp(x + 1, y + 1, s, p);
return f[x][y] = ans;
}
};
生不出人，我很抱歉
晕，好不容易搞清楚了递推公式，但这个dp是干啥的啊。。。还有y总的思路压根想不到啊，菜醒。。
这是用记忆化搜索来实现的。也可以用循环来实现：
感谢y总，为y总打call！！！！ORZ
最后一个条件判断里 那么多&& || 真的很难理解啊
i && 的作用是什么
哦我懂了 i && 是用来限制的 i = 0时只要考虑f[i][j - 2] 针对于s = ‘’ p = ‘.*’的情况
y总，这个地方，样例给的“aaa”可以和”abaca“匹配。我看着不匹配啊。可以解释下么😂，除非反着匹配 ，正着匹配我始终觉得不匹配
我看了很久再看了看题解终于看懂了，”*”代表的是他前面的那一个字符可以出现任意次，这样b和c都出现0次就可以理解了，匹配了
转态表示：f[i][j] 表示s[i,…]和p[j,…]相匹配
状态转移：
1、p[j]是正常字符，f[i][j]=s[i]==p[j]&&f[i+1][j+1];
2、p[j]是”.”，f[i][j]=f[i+1][j+1]
3、p[j+1]是”*”，s[i]==p[j]&&f[i][j]=f[i+1][j]||f[i][j+2]
注意点：
1.记忆化搜索
2.由于是从后往前进行递推判断，所以需要用到递归
对滴，总结得不错！
赞！
我个人不赞成f[i][j]用来存suffixes的匹配程度，
例如 s = “aab” p =”.*b”
p 的suffix “*b”没有意义.所以这道题目完全可以正过来写。
if (f[x][y] != -1) return f[x][y];
这句代码去掉也能成功。我咋感觉不会重复调用f(x,y)呢？不是每一次都会线性增加x或者y吗？
要是aaa与abbbb*aa匹配不
不匹配，* 表示他前面的字符可以出现0或n次。那么abbbb * aa ,可以看成 abbbaa,如果要匹配，要改成ab * b * b * b * aa
想知道当 p[j - 1] = ‘*’，第一种情况和第二种情况应该没有交集吧？应该不会出现第一种情况满足了，然后第二种情况又满足的情况吧？
y总，想问下这段代码
改成
···
if(x== n) return f[x][y] = y==m;
```
为什么会报错啊，求解
s遍历完了，p结尾还可能有，比如结尾为 a*，即字母 + 星号 ，当星号表示 0 个时也是正确的
bool isMatch(char s, char p) {
int sn=strlen(s),pn=strlen(p),i=0,j=0,t;
while(i<sn && j<pn){
if(p[j]==’.’){
if(j+1<pn && p[j+1]==’’) return true;
else{
i;
j;
}
}
else{
if(p[j]==s[i]){
t=s[i];
i;
if(j+1<pn && p[j+1]==’*’){
while(i<sn && s[i]==s[i-1]) i;
j+=2;
while(p[j]==t) j;
}
else j;
}
else if(j+1<pn && p[j+1]==’’) j+=2;
else break;
}
}
if(sn==0){ //前者为空时
while(j<pn){
if(p[j]==’‘ || (j+1<pn && p[j+1]==’’)) j++;
else break;
}
}
if(i==sn && j==pn) return true;
else return false;
}
修改了一下 萌新代码真的丑陋 辛苦大佬
bool isMatch(char s, char p) {
int sn=strlen(s),pn=strlen(p),i=0,j=0;
// printf(“%d %d\n”,sn,pn);
while(i<sn && j<pn){
if(p[j]==’.’){
if(j+1<pn && p[j+1]==’’) return true;
else{ i; j;}
}
else{
if(p[j]==s[i]){
i;
if(j+1<pn && p[j+1]==’*’){
while(i<sn && s[i]==s[i-1]) i;
j+=2;
}
else j;
}
else if(j+1<pn && p[j+1]==’’) j+=2;
else break;
}
}
if(sn==0){ //前者为空时
while(j<pn){
if(p[j]==’‘ || (j+1<pn && p[j+1]==’*’)) j;
else break;
}
}
if(i==sn && j==pn) return true;
else return false;
}
代码AC了 但是我觉得 ”aaab” “aab” 我写的这个会返回false 正确应该是true
刚跨考的萌新 求大佬指点一下
i && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.')这段里的这个
f[i - 1][j]是什么意思呢？为什么要用ans暂时储存呢？ 在计算中不会再次访问到f[x][y]吧
ans这个变量比f[x][y]短一点。请问，如果string 已经到了s[n]位置 ，而exp还没有到p[m]位置，这种边界情况似乎没考虑进去
代码的这部分写得比较绕，这里的判断藏在
first_match里了，只有当x < n的时候才会等于true，也才会执行x + 1的递归，所以处理过程中是不会越界的。楼主写的太漂亮，完美
谢谢hh
再补充下
很棒hh
yls这里的递归解法就是指dfs吗？用dfs不用动归也可以解，时间复杂度都是o(nm)吗？
这里的dfs也叫记忆化搜索，保证了每个
f[x][y]都只会被计算一次，所以时间复杂度是 $o(nm)$。纯暴力搜索不加记忆化的话，时间复杂度就是指数级别了。理解了，没有意识到这是记忆化搜索的应用，谢谢yls！
if (y + 1 < m && p[y + 1] == ‘*’)
{
ans = dp(x, y + 2, s, p) || first_match && dp(x + 1, y, s, p);
这里的else不是也可能否定y + 1 < m这个判断条件么，为什么没报数组下标出界异常？
p的下标只能到m - 1，但f的下标可以到m。为什么这里把
写成
就会出现段错误
调整顺序之后可能会导致数组下标越界：当
x == n的时候也会递归到下一层了，那么此时x = n + 1，就会越界了。这个题怎么写非递归的？我写了半天没写出来
非递归版本可以参考这份代码LeetCode 10，题目是一样的。
不过状态表示稍微调整了一下：
f[i][j]表示p[1~j]，是否能匹配s[1~i]。两种表示方式都是可以的。