原題鏈接

字符串匹配問題考慮LCS問題，對于i-1的狀態(tài)，必須保證i>=1,且對于p[j]==' . '，都成立的匹配

class Solution {
public:
    bool isMatch(string s, string p) {
        int n=s.size(),m=p.size();
        s=' '+s,p=' '+p;
        vector<vector<bool>>dp(n+1,vector<bool>(m+1));
        dp[0][0]=true;//一個(gè)字符都沒有的時(shí)候，顯然是匹配的
        //第一個(gè)串是空的，第二個(gè)串非空，存在這種情況,因此第一個(gè)串的長度>=0
        //但是若第一個(gè)串是非空，第二個(gè)串是空的，則不存在，因此第二個(gè)串的長度>=1
        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]!='*')//p[j]不為'*'時(shí)，i無法任意匹配，從1開始
                    dp[i][j]=dp[i-1][j-1]&&(s[i]==p[j]||p[j]=='.');
                else if(p[j]=='*')
                    dp[i][j]=dp[i][j-2]||i&&dp[i-1][j]&&(s[i]==p[j-1]||p[j-1]=='.');
                
            }
        }
        return dp[n][m];
    }
};