Sword finger offer19 regular expression

subject

Please implement a function to match the contains ’. ‘ and ’‘ Regular expression of .** Characters in pattern ’.‘ Represents any character , and ’' Indicates that the character in front of it can appear any number of times （ contain 0 Time ）**. In the subject , Matching means that all characters of a string match the whole pattern . for example , character string "aaa" With the model "a.a" and "abaca" matching , But with "aa.a" and "ab*a" No match .
Example ：

set up s The length of is n , p The length of is m ; take s Of the i Characters are marked as s_i ,p Of the j Characters are marked as p_j , take s Before ii The substring composed of characters is recorded as s[:i] , In the same way p Before j The substring composed of characters is recorded as p[:j] .
-------> It can be transformed into seeking s[:n] Can you and p[:m] matching .
--------> It's from s[:1] and p[:1] Whether it can match starts to judge , Add one character per round and judge whether it can match , Until the complete string is added s and p . Expand to see , hypothesis s[:i] And p[:j] Can match , Then there are two states ：

1. Add a character s_{i+1} Whether it can match ？
2. Add characters p_{j+1} Whether it can match ？

Dynamic planning analysis

State definition ： Let's set the dynamic programming matrix dp , dp[i][j] Representative string s Before i Characters and p Before j Whether the characters match .
Transfer equation ： 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]
initialization ：
initialization ： You need to initialize dp First row of matrix , To avoid index out of bounds during state transition .
dp[0][0] = true： Represents that two empty strings can match .
dp[0][j] = dp[0][j - 2] And p[j - 1] = ‘*’： First line s Is an empty string , So when p The even digits of are * Can match （ That is to let p The odd digits appear 0 Time , keep p Is an empty string ）. therefore , Loop through the string p , In steps of 2（ That is, only look at even digits ）.

Code

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;
        // initialization 
        for(int j = 2; j < n; j +=2){
    
            dp[0][j] = dp[0][j-2] && p.charAt(j-1) == '*';
        }
        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;
                    else if(dp[i-1][j] && s.charAt(i-1) == p.charAt(j-2)) dp[i][j] = true;
                    else if(dp[i-1][j] && p.charAt(j-2) == '.')  dp[i][j] = true;
                }else{
    
                    if(dp[i-1][j-1] && s.charAt(i-1) == p.charAt(j-1)) dp[i][j] = true;
                    else if(dp[i-1][j-1] && p.charAt(j-1) == '.' ) dp[i][j] = true;
                }
            }
        }
        return dp[m-1][n-1];

    }
}