动态规划

基于闫式dp分析法。


综上 ,
f[i][j]={f[i−1][j−1]&&(s[i]==p[j]∣∣′.′==p[j])if  p[j]≠∗f[i][j−2]∣∣(f[i−1][j]&&(s[i]==p[j−1]∣∣′.′==p[j−1])if  p[j]=∗f[i][j] = \begin {cases} f[i-1][j-1] ~~\&\& ~~(s[i]==p[j] ~||~ '.'==p[j])&\text{ if }~p[j]\neq * \\ f[i][j-2] ~~||~~(f[i-1][j] ~~\&\&~~(s[i] == p[j-1] ~~||~~'.'==p[j-1])&\text{ if }~p[j]=* \end{cases}f[i][j]={f[i−1][j−1]  &&  (s[i]==p[j] ∣∣ ′.′==p[j])f[i][j−2]  ∣∣  (f[i−1][j]  &&  (s[i]==p[j−1]  ∣∣  ′.′==p[j−1])​ if  p[j]​=∗ if  p[j]=∗​

上式用代码表示

	if('*'!=p[j]) f[i][j] = i && f[i-1][j-1] && (p[j]==s[i]||p[j]=='.'); // i = 0 时，i -1 越界else if('*'==p[j]) {if(i) f[i][j] = f[i][j-2] || (f[i-1][j]&&(s[i]==p[j-1]||'.'==p[j-1]));//i=0 时，i-1越界else f[i][j] = f[i][j-2];}

优化dp

class Solution {
public:bool isMatch(string s, string p) {int n = s.size();int m = p.size();s = ' '+s,p = ' '+p;//f[0][0]表示s空p空,为了下标对应，s和p后移一格vector> f(n+1,vector(m+1));//f[i][j],表示所有s[1~i]和p[1~j]的匹配方案f[0][0] = true;//s空p空 , 有一种匹配方案for(int i = 0;i<=n;i++)for(int j = 1;j<=m;j++){if(j+1<=m&&'*'==p[j+1]) continue;//p[j+1]=='*' , 那么p[j]可以取0个，跳过p[j]的判断。if('*'!=p[j]) f[i][j] = i && f[i-1][j-1] && (p[j]==s[i]||p[j]=='.'); // i = 0 时，i -1 越界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];}
}; 

时间复杂度 O(n×m)O(n\times m)O(n×m) ， nnn 是 sss 的长度，mmm 是 ppp 的长度 ， 状态转移的时间复杂度 O(n×m)O(n\times m)O(n×m)。

空间复杂度 O(n×m)O(n\times m)O(n×m) dpdpdp 数组的空间复杂度 O(n×m)O(n\times m)O(n×m) 。

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC