[Hot100]10. Regular Expression Matching

10. Regular Expression Matching
Difficult questions
Dynamic programming ：
dp[i][j] Express s Before i Can the p Before j A match

● Transfer equation ： We need to pay attention to , because dp[0][0] Represents the status of empty characters , therefore dp[i][j] The corresponding added character is s[i - 1] and p[j - 1] .
○ When p[j - 1] = ‘*’ when , dp[i][j] In the case of true When is equal to the true ：
■ dp[i][j-2]
● Combine characters p[j - 2] * As if 0 When the time , Can it match ;
■ dp[i-1][j]
● And p[j - 2] = s[i - 1]： Instant character p[j - 2] There are more 1 When the time , Can it match ;
● And p[j - 2] = ‘.’： Instant character ‘.’ There are more 1 When the time , Can it match ;

○ When p[j - 1] != ‘*’ when , dp[i][j] In the case of true When is equal to the true ：
■ dp[i - 1][j - 1]
● And s[i - 1] = p[j - 1]： Instant character p[j - 1] When it occurs more than once , Can it match ;
● And p[j - 1] = ‘.’： I'm going to change the character . Treat as character s[i - 1] when , Can it match ;

class Solution {
    
    public boolean isMatch(String s, String p) {
    
        int m = s.length() + 1, n = p.length() + 1;
        boolean[][] dp = new boolean[m][n];
        dp[0][0] = true;
        //  Initialize first line 
        for(int j = 2; j < n; j += 2)
            dp[0][j] = dp[0][j - 2] && p.charAt(j - 1) == '*';
        //  State shift 
        for(int i = 1; i < m; i++) {
    
            for(int j = 1; j < n; j++) {
    
                if(p.charAt(j - 1) == '*') {
    
                    if(dp[i][j - 2]) dp[i][j] = true;                                                          
                    // 1.
                    else if(dp[i - 1][j] && s.charAt(i - 1) == p.charAt(j - 2)) dp[i][j] = true; // 2.
                    else if(dp[i - 1][j] && p.charAt(j - 2) == '.') dp[i][j] = true;             // 3.
                } else {
    
                    if(dp[i - 1][j - 1] && s.charAt(i - 1) == p.charAt(j - 1)) dp[i][j] = true;  // 1.
                    else if(dp[i - 1][j - 1] && p.charAt(j - 1) == '.') dp[i][j] = true;         // 2.
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}

class Solution {
    
    public boolean isMatch(String s, String p) {
    
        int m = s.length();
        int n = p.length();

        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
    
            for (int j = 1; j <= n; ++j) {
    
                if (p.charAt(j - 1) == '*') {
    
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
    
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else {
    
                    if (matches(s, p, i, j)) {
    
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }

    public boolean matches(String s, String p, int i, int j) {
    
        if (i == 0) {
    
            return false;
        }
        if (p.charAt(j - 1) == '.') {
    
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
}