One brush 149 force deduction hot question-10 regular expression matching (H)

 subject ：
 Give you a string  s  And a character rule  p, Please come to realize a support  '.'  and  '*'  Regular expression matching .

'.'  Match any single character 
'*'  Match zero or more previous elements 
 Match , Is to cover   Whole   character string  s Of , Instead of partial strings .
-------------
 Example ：
 Input ：s = "aa", p = "a"
 Output ：false
 explain ："a"  Can't match  "aa"  Whole string .
 Example  2:

 Input ：s = "aa", p = "a*"
 Output ：true
 explain ： because  '*'  Represents the element that can match zero or more preceding elements ,  The element in front of here is  'a'. therefore , character string  "aa"  Can be regarded as  'a'  I repeated it once .
 Example  3：

 Input ：s = "ab", p = ".*"
 Output ：true
 explain ：".*"  Means zero or more can be matched （'*'） Any character （'.'）.

 Tips ：

1 <= s.length <= 20
1 <= p.length <= 30
s  Only from  a-z  Lowercase letters of .
p  Only from  a-z  Lowercase letters of , As well as the character  .  and  *.
 Ensure that characters appear every time  *  when , All of them are matched with valid characters 
--------------------
 reflection ：
 If you sweep from left to right 
 Whether the character is followed by an asterisk will affect the result , It's a little complicated to analyze .

 Select scan from right to left 
 There must be a character in front of the asterisk , The asterisk only affects this character , It's like a copier .

s、p  Whether the string matches , Depending on ： Whether the rightmost end matches 、 Whether the remaining substrings match .
 It's just that the rightmost end may be a special symbol , It needs to be discussed according to the situation .

 Express subproblems in general 
 Whether the big substring matches , Whether it matches the remaining substrings , It's the same problem with different scales .

 situation 1：s[i-1]s[i−1]  and  p[j-1]p[j−1]  It is a match. 
 The rightmost character is matched , that , The answer to the big question  =  Whether the remaining substrings match .

 situation 2：s[i-1]s[i−1]  and  p[j-1]p[j−1]  It doesn't match 
 The right end does not match , You can't be sentenced to death —— May be  p[j-1]p[j−1]  Mismatch caused by asterisk , The asterisk is not a real character , It doesn't match and doesn't count .
 If  p[j-1]p[j−1]  Not an asterisk , Then it really doesn't match .

p[j-1]=="*"p[j−1]=="∗", And  s[i-1]s[i−1]  and  p[j-2]p[j−2]  matching 
p[j-1]p[j−1]  It's an asterisk , also  s[i-1]s[i−1]  and  p[j-2]p[j−2]  matching , There are three situations to consider ：
p[j-1]p[j−1]  The asterisk can make  p[j-2]p[j−2]  stay  p  Disappear in the string 、 appear  1  Time 、 appear  >=2  Time .
 As long as one of them makes the remaining substrings match , That will match , See the picture below  a1、a2、a3.

a3  situation ： hypothesis  s  At the right end of the is a  a,p  The right end of is  a * ,*  Give Way  a  repeat  >= 2  Time 
 The asterisk is not a real character ,s、p match , Want to see  s  Remove the end of  a,p  Remove the last one  a, Whether the rest match .
 The asterisk is copied  >=2  individual  a, Take one , be left over  >=1  individual a,p  The end is still  a*  It hasn't changed .
s  Last  a  Offset by , Continue to investigate  s(0,i-2)  and  p(0,i-1)  match .

p[j-1]=="*", but  s[i-1]  and  p[j-2] Mismatch 
s[i-1] and  p[j−2] Mismatch , There's still hope ,p[j−1] The asterisk can kill  p[j−2], Continue to investigate  s(0,i-1) and  p(0,j-3)

base case
p For the empty string ,s It's not empty string , It's definitely not a match .
s For the empty string , but p It's not empty string , To match , It can only be the asterisk at the right end , It kills a character , hold  p  Become empty string .
s、p All empty strings , Definitely match .

 Code ：
class Solution {
    
    public boolean isMatch(String s, String p) {
    
        char[] cs = s.toCharArray();// Convert string to character array 
        char[] cp = p.toCharArray();

        //dp[i][j]: Express  s Before i Characters , p Before j Whether characters can match 
        boolean[][] dp = new boolean[cs.length + 1][cp.length + 1];
        // Initial value 
        //s It's empty  p It's empty   To match 
        dp[0][0] = true;
        //p It's empty  s Not empty   It has to be for false （boolean The default value of the type array is false, No need to deal with ）
        //s It's empty  p Not empty   because * Can match 0 Characters , So it's possible for true
        for (int j = 1; j <= cp.length; j++) {
    
            if (cp[j - 1] == '*') {
    
                dp[0][j] = dp[0][j - 2];
            }
        }
        //  Fill in the grid 
        for (int i = 1; i <= cs.length; i++) {
    
            for (int j = 1; j <= cp.length; j++) {
    
                //  The last character of text string and pattern string can match 
                if (cs[i - 1] == cp[j - 1] || cp[j - 1] == '.') {
    
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (cp[j - 1] == '*') {
     //  The last bit of the pattern string is *
                    //  Pattern string * The first character of can match the last bit of the text string 
                    if (cs[i - 1] == cp[j - 2] || cp[j - 2] == '.') {
    
                        dp[i][j] = dp[i][j - 2]      // * matching 0 The next situation 
                                || dp[i - 1][j];     // * matching 1 One or more times 
                    } else {
     //  Pattern string * The first character of cannot match the last bit of the text string 
                        dp[i][j] = dp[i][j - 2];     // * Only match 0 Time 
                    }
                }
            }
        }
        return dp[cs.length][cp.length];
    }
}

LC