LeetCode 10. 正则表达式匹配

LeetCode 10. 正则表达式匹配

思路：

以p[j]是否为'*'划分，

代码：

class Solution {
public:
    bool isMatch(string s, string p) {
        //Dp
        int n = s.size(),m = p.size();
        s = ' ' + s;
        p = ' ' + p;
        
        vector<vector<bool>> f(n + 1, vector<bool> (m + 1));

        f[0][0] = true;

        for(int i = 0; i <= n; i++){
            //j == 0 开始没有意义
            for(int j = 1; j <= m; j++){
                //如果p当前的字符的下一个字符是* 需要在一起判断 所以当前不需要判断
                if(j + 1 <= m && p[j + 1] == '*') continue;
                if(i && p[j] != '*'){
                    f[i][j] = (s[i] == p[j] || p[j] == '.') && f[i - 1][j - 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];
    }
};