Leetcode buckle -10 Regular expression matching analysis [recursion and dynamic programming]

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 1：
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 （’.’）.
Example 4：
Input ：s = “aab” p = “cab”
Output ：true
explain ： because '’ Represents zero or more , here ‘c’ by 0 individual , ‘a’ Be repeated once . So you can match strings “aab”.
Example 5：
Input ：s = “mississippi” p = "misisp."
Output ：false
Tips ：
0 <= s.length <= 20
0 <= p.length <= 30
s May is empty , And contains only from a-z Lowercase letters of .
p May is empty , And contains 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
---------------
source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/regular-expression-matching
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

recursive

We first define a method m(String s, String p) Represents the incoming string s And character regularity p match , return boolean

This topic is in my hands , The first thing I think of is recursion . Step by step analysis ：

Because the subject said ,s and p May be empty , Then first judge s and ( perhaps )p Empty situation

explain ：s-1 ,p-1 ,p-2 Indicates that the end of the string is truncated 1 Bit or end 2 position

1. If s and p All is empty , Then return to true
2. If p It's empty , You must return to false, Because at this time s Not empty , Never match
3. If s It's empty , also p With * ending （ such as .* perhaps x*）,m(s, p) = m(s, p-2) At this time, it is equivalent to .* perhaps x* Nothing matches , otherwise m(s, p) = false

Consider the case that none of them is empty ：

It is still necessary to briefly explain how the above equation is obtained , about s and p, If there is s And p The match , that

1. matching 0 Time , Get rid of p End character of
2. matching 1 Time , Get rid of s End character of perhaps At the same time to remove s/p End character of （ matching 1 Lose it once ）

stay p With * At the end , Why not remove at the same time s/p The last character of ？ Because this situation has been included :

Code implementation

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

            if (s.equals(p)) {
    
                return true;
            }
            if ("".equals(p)) {
    
                return false;
            }
            if ("".equals(s)) {
    
                if (p.endsWith("*")) {
    
                    return isMatch(s, p.substring(0, p.length() - 2));
                } else return false;
            }
            
            if (p.endsWith("*")) {
    
                if (p.charAt(pLen - 2) == '.') {
    
                    // 1. p Follow s matching   Get rid of s At the end of 
                    return isMatch(s.substring(0, sLen - 1), p) ||
                            // 2. p Follow s matching   Get rid of p At the end of 
                            isMatch(s, p.substring(0, pLen - 2))
                            ;
                } else if (p.charAt(pLen - 2) == s.charAt(sLen - 1)) {
    
                    // 1. p Follow s matching   Get rid of s At the end of 
                    return isMatch(s.substring(0, sLen - 1), p) ||
                            // 2. p Follow s matching   Get rid of p At the end of 
                            isMatch(s, p.substring(0, pLen - 2))
                            ;
                } else {
    
                    // 3. p Follow s Mismatch   Get rid of p At the end of 
                    return isMatch(s, p.substring(0, pLen - 2));
                }
            } else if (p.endsWith(".")) {
    
                // 4.  Not * End matching   Remove the last digit respectively 
                return isMatch(s.substring(0, sLen - 1), p.substring(0, pLen - 1));
            } else {
    
                if (s.charAt(sLen - 1) == p.charAt(pLen - 1)) {
    
                    // 4.  Not * End matching   Remove the last digit respectively 
                    return isMatch(s.substring(0, sLen - 1), p.substring(0, pLen - 1));
                } else return false;
            }
        }
    }

Dynamic programming

Three characteristics of dynamic programming

1. Optimal substructure The optimal substructure refers to , The optimal solution of the problem includes the optimal solution of the subproblem . On the contrary, it means , We can get the optimal solution of the subproblem , Deduce the optimal solution of the problem . The state of the later stage can be derived from the state of the previous stage .
2. No aftereffect No aftereffect has two meanings , The first meaning is , In deriving the state of the later stage , We only care about the state value of the previous phase , I don't care how this state is derived step by step . The second meaning is , Once the state of a certain stage is determined , It will not be affected by the decision-making in the later stage . No aftereffect is a very “ loose ” The requirements of . As long as the dynamic programming problem model mentioned above is satisfied , In fact, they will basically meet the requirement of no aftereffect .
3. Repeat the question Different decision sequences , When you reach the same stage , There may be repetitive States .

Dynamic planning solution ideas ：

1. State transition equation ： The state transfer equation method is a bit similar to the idea of recursion . We need to analyze , How to solve a problem recursively through subproblems , The so-called optimal substructure . According to the optimal substructure , Write recursive formulas , That is, the so-called state transition equation . With the state transition equation , The code implementation is very simple . In general , We have two code implementation methods , One is recursion plus “ Memorandum ”, The other is iterative recursion .
2. State transition table ： Let's draw a status table first . State tables are generally two-dimensional , So you can think of it as a two-dimensional array . among , Each state contains three variables , That's ok 、 Column 、 Array value . According to the decision-making process , Before and after , According to the recurrence relation , Fill in each state in the state table in stages . Last , We'll take this recursive process of filling in the form , Translate into code , It's dynamic programming code .

This solution process , We use the state transition equation , Because the equation is easier to understand , And drawing tables is a little troublesome .

We need to define a binary array to store s/p At different index bits , The corresponding matching . such as boolean mem[sLen+1][pLen+1], Why don't dimensions follow s/p The same length ？ because s/p May be empty , So the extra length 1 In fact, it means s/p It's empty The situation of .

Summarize the above process ：

1. p With * result ,a/b/c In three cases ： hold f(i, j) = f(i, j-2) extracted , And then, according to the matching situation, take || f(i-1, j) Result
2. Not * ending ,s And p End match ,f(i,j) = f(i-1,j-1)
3. Other situations , Can't match f(i,j) = false;
4. understand s And p The matching process , It is derived from the back to the front , The assignment process of two-dimensional array is from front to back , Because the latter state depends on the result calculated above ;

Code implementation

class Solution {
    
   public boolean isMatch(String s, String p) {
    
       int sLen = s.length();
       int pLen = p.length();
       //  Define a two-dimensional array   Store respective bit characters s And regular p Matching results 
       //  Because of existence p perhaps ( and )s by 0 The situation of   So the latitude ratio of a two-dimensional array s/p More length 1
       boolean[][] mem = new boolean[sLen + 1][pLen + 1];
       // s and p All for 0 The situation of   It can be matched 
       mem[0][0] = true;
       //  There is a problem that needs attention 
       // i/j It's not s/p The index of the bit   You need to subtract 1 Is the index bit 
       for (int i = 0; i <= sLen; i++) {
    
           //  Why not let j=0 Well , because j=0 When   It must be unmatched 
           for (int j = 1; j <= pLen; j++) {
    
               if (p.charAt(j - 1) == '*') {
    
                   //  When  *  While in existence   Regardless of  *  The preceding character is the same as s Whether the bit characters match 
                   //  The result of the calculation method is to bring   Of the following expression   Why?  ？
                   //  If 1. * The front is . perhaps * The preceding character is the same as s The characters match   that 
                   // mem[i][j] = mem[i - 1][j] || mem[i][j - 2] ;
                   //  If 2. * The preceding character is the same as s There is a character mismatch between   that 
                   // mem[i][j] = mem[i][j - 2];
                   mem[i][j] = mem[i][j - 2];
                   
                   //  Why? j - 1 Well  ？  Because what I need to judge is  *  The one in front   also j - 1 It must not overflow (* There must be a character in front of it )
                   if (matches(s, p, i, j - 1)) {
    
                       mem[i][j] = mem[i - 1][j] || mem[i][j];
                   }
               } else if (matches(s, p, i, j)) {
    
                   mem[i][j] = mem[i - 1][j - 1];
               }
           }
       }
       return mem[sLen][pLen];
   }

   private 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);
   }
}