正则表达式匹配

原题链接

字符串匹配问题考虑LCS问题，对于i-1的状态，必须保证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;//一个字符都没有的时候，显然是匹配的
        //第一个串是空的，第二个串非空，存在这种情况,因此第一个串的长度>=0
        //但是若第一个串是非空，第二个串是空的，则不存在，因此第二个串的长度>=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]不为'*'时，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];
    }
};