LeetCode 10. Regular Expression Matching

LeetCode 10. Regular Expression Matching

Dynamic programming

const int N = 25, M = 35;
class Solution {
    
public:
    bool f[N][M] = {
    false}; // s front i And p front j matching 
    bool isMatch(string s, string p) {
    
        int n = s.size(), m = p.size();
        s = " " + s, p = " " + p; 
        
        //  Initialization conditions , Only the last character is * Can match only when 
        f[0][0] = true;
        for(int i = 1; i <= m; i ++)
            if(p[i] == '*')
                f[0][i] = f[0][i - 2];

        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
            {
    
                if(j + 1 <= m && p[j + 1] == '*') continue;
                if(p[j] != '*')  // No * And matching 
                    f[i][j] = f[i - 1][j - 1] &&(s[i] == p[j] || p[j] == '.');
                if(p[j] == '*') // yes *, And divided into representatives 1 Characters , Two characters , Three characters ....
                    f[i][j] = f[i][j - 2] || f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.');
            }
        return f[n][m];
    }
};