leetcode 10. Regular expression matching regular expression matching (difficult)

One 、 The main idea of the topic

label :  Dynamic programming

https://leetcode.cn/problems/regular-expression-matching

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

'.'  Match any single character '*'  Matching zero or more previous elements is called matching , 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 （'.'）.

Tips ：

• 1 <= s.length&nbsp;<= 20

• 1 <= p.length&nbsp;<= 30

• s&nbsp; Only from &nbsp;a-z&nbsp; Lowercase letters of .

• p&nbsp; Only from &nbsp;a-z&nbsp; Lowercase letters of , As well as the character &nbsp;.&nbsp; and &nbsp;*.

• Ensure that characters appear every time &nbsp;*  when , All of them are matched with valid characters

Two 、 Their thinking

Define a two-dimensional array dp, among dp[i][j] Representation string s The string of s[0, i] Whether it can be string p The string of p[0,j] matching , According to different cases of regular expressions , Namely the asterisk 、 Order number 、 Characters other than asterisk and dot , We can update it by discussing the situation dp Array .

3、 ... and 、 How to solve the problem

3.1 Java Realization

public class Solution2 {
 public boolean isMatch(String s, String p) {
 int m = s.length();
 int n = p.length();
 boolean[][] dp = new boolean[m + 1][n + 1];
 dp[0][0] = true;
 for (int i = 1; i < n + 1; i++) {
 if (p.charAt(i - 1) == '*') {
 //  asterisk   Not on page 1 A place
 dp[0][i] = dp[0][i - 2];
 }
 }
 for (int i = 1; i < m + 1; i++) {
 for (int j = 1; j < n + 1; j++) {
 //  The last wildcard may be   Order number 、 asterisk 、 character
 if (p.charAt(j - 1) == '.') {
 //  The last wildcard is   Order number
 dp[i][j] = dp[i - 1][j - 1];
 } else if (p.charAt(j - 1) != '*') {
 //  The last wildcard is not   asterisk
 dp[i][j] = dp[i - 1][j - 1] && p.charAt(j - 1) == s.charAt(i - 1);
 } else if (p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.') {
 dp[i][j] = dp[i][j - 2];
 } else {
 dp[i][j] = dp[i][j - 1] || dp[i - 1][j] || dp[i][j - 2];
 }
 }
 }
 return dp[m][n];
 }
}


Four 、 Summary notes

• 2022/7/5  people follow the example of their superiors , The emperor's new dress