LC.44. 通配符匹配(DP)

传送门

思路： d p dp dp。这里根据题解再梳理一遍。

显然可以令 d p [ i ] [ j ] dp[i][j] dp[i][j]为 s s s前 i i i个字符和 p p p前 j j j个字符是否匹配。

首先我们考虑状态转移方程。

1.显然当 p [ j − 1 ] = = ′ ? ′ p[j-1]=='?' p[j−1]==′?′或者 s [ i − 1 ] = = p [ j − 1 ] s[i-1]==p[j-1] s[i−1]==p[j−1]可以直接由 d p [ i − 1 ] [ j − 1 ] dp[i-1][j-1] dp[i−1][j−1]转移过来

即： d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] dp[i][j]=dp[i-1][j-1] dp[i][j]=dp[i−1][j−1].

2.如果 p [ j − 1 ] = = ′ ∗ ′ p[j-1]=='*' p[j−1]==′∗′，显然可以由 d p [ i − 1 ] [ j ] 和 d p [ i ] [ j − 1 ] dp[i-1][j]和dp[i][j-1] dp[i−1][j]和dp[i][j−1]转移过来。

即对应 ∗ * ∗是否为空串，若是空串直接由 d p [ i ] [ j − 1 ] dp[i][j-1] dp[i][j−1]转移。

否则不是空串，因为 ∗ * ∗可变为任意字符串所以必能由 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i−1][j]转移。

其他情况都不能转移。

再考虑边界情况，显然 d p [ 0 ] [ 0 ] = 1 , d p [ i ] [ 0 ] = 0 , ( i > 0 ) dp[0][0]=1,dp[i][0]=0,(i>0) dp[0][0]=1,dp[i][0]=0,(i>0)

d p [ 0 ] [ i ] dp[0][i] dp[0][i]，需要考虑前 i i i个字符是否都为 ∗ * ∗，若出现 ? ? ?或字母则 d p [ 0 ] [ i ] = 0 dp[0][i]=0 dp[0][i]=0。

时间复杂度： O ( n m ) O(nm) O(nm)

class Solution {
public:
    bool isMatch(string s, string p) {
        int m=s.size(),n=p.size();
        vector<vector<bool> >dp(m+1,vector<bool>(n+1));
        dp[0][0]=1;
        for(int i=1;i<=n;i++)
            if(p[i-1]=='*') dp[0][i]=1;
            else break;
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
                if(s[i-1]==p[j-1]||p[j-1]=='?') dp[i][j]=dp[i-1][j-1];
                else if(p[j-1]=='*') dp[i][j]=dp[i-1][j]|dp[i][j-1];
            return dp[m][n];
    }
};

A C AC AC自动机知识待补 … … \dots\dots ……