剑指 Offer 19. 正则表达式匹配（困难）

题目：

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size()+1, n = p.size()+1;
        vector<vector<bool>> dp(m, vector<bool>(n, false));      //设动态规划矩阵 dp ， dp[i][j] 代表字符串 s 的前 i 个字
        dp[0][0] = true;                                         //符和 p 的前 j 个字符能否匹配
        for(int j=2;j<n;j+=2){      //由于dp[0][0]代表的是空字符的状态，因此dp[i][j]对应的添加字符是s[i - 1]和p[j - 1]
            dp[0][j] = dp[0][j-2]&&p[j-1]=='*';      //只要初始化首行：s为空，p的偶数个为'*'时就匹配。首列一定不匹配。
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(p[j-1]=='*'){
                    if(dp[i][j-2]) dp[i][j] = true;      // aaa|   aaa|b*
                    else if(dp[i-1][j]&&p[j-2]==s[i-1]) dp[i][j] = true;      // aaa|a   aa*|
                    else if(dp[i-1][j]&&p[j-2]=='.') dp[i][j] = true;      // aaa|a   a.*|
                }
                else{
                    if(dp[i-1][j-1]&&p[j-1]==s[i-1]) dp[i][j] = true;      // aa|b   aa|b
                    if(dp[i-1][j-1]&&p[j-1]=='.') dp[i][j] = true;      // aa|b   aa|.
                }
            }
        }
        return dp[m-1][n-1];
    }
};

作者：Krahets
链接：https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solutions/494128/jian-zhi-offer-19-zheng-ze-biao-da-shi-pi-pei-dong/
来源：力扣（LeetCode）