“This is the 20th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

The title

  • 10. Regular expression matching
  • Topic describes

Given a string s and a character rule P, implement a regular expression match that supports ‘.’ and ‘*’.

‘.’ matches any single character.’ *’ matches zero or more of the preceding elements.

  • Example 1:

Input: s = “aa” p = “a” Output: false Description: “A” cannot match the entire string “aa”

  • Example 2:

Input: s = “aa” p = “a*” Output: true Thus, the string “aa” can be treated as ‘a’ repeated once.

  • Example 3

Input: s = “ab” p = “.” Output: true Description: “.*” indicates that zero or more (“) characters (‘.’) can be matched.

parsing

First of all, we can find that this is an obvious problem of dynamic programming, but the problem of state transition equation is really a bit difficult to think about, so let’s go through it together

What does dp[I][j] represent

Dp [I][j]: indicates whether the first I characters of string s match the first j characters of string P. The result is a Boolean type

Analyzing state transitions

For the string p, there are three possibilities:

  • Lowercase letters: Because they are lowercase letters, you only need to determine whether S [I] is equal to P [j]
    • If s[I] == p[j], dp[I][j] = dp[i-1][J-1]
    • If s [I]! = p[j], dp[I][j] = false
  • The dot.: can match any character,dp[i][j] = dp[i – 1][j – 1];
  • The asterisk*

Asterisks are tricky, so let’s pull them out separately

  1. Analyze the asterisk situation

The asterisk means it can match zero or more times

  • S [I] does not match p[j-1] : For a mismatch, the following conditions should be met, s[I]! = p[j-1] and p[j-1]! P [I][j] = p[I][j]

  • S [I] match with P [j-1] : there are two cases, can be multiple match (DP [I][j] = DP [I][j] = DP [I][J]), may be matched once (DP [I][j] = DP [I][J-1]), but the multiple match case includes the matching once.

    Here’s an example to further illustrate this point:

    S = “AFS”, p = “AFS *”

    Match multiple times: DP [3][4] = DP [2][4]

    Match once: DP [3][4] = DP [3][3]

    Dp [2][4] is a direct match between p and s, but dp[3][3] is a direct match.

    So we can get the conclusion in this case: dp[I][j] = dp[i-1][j]?

    As in the case of mismatch, we have missed the case where p[j-1] = ‘.’. Here is another example

    S = “ab”, p = “ab.*”,

    Dp [2][4] = dp[1][4] = dp[2][2]

    Therefore, the correct conclusion is that the dp [I] [j] = dp [j] [I – 1] | | dp [I] [j – 2];

Edge cases

  1. dp[0][0] = true;
  2. dp[i][0] = false; (i > 0)
  3. Dp [0][j](j > 0) may be true

conclusion

After analyzing the above part, in fact, the context of the whole topic is very clear, just need to translate the above analysis process into code.

Past wonderful articles

  • Cow guest latest front-end JS written test 100 questions
  • The latest front end of the interview questions summary (including analysis)
  • Grab the latest front end test five hundred data analysis JS interview hot spots
  • Happy cat stroking for VSCode and website adoptive cats
  • Native JavaScript soul Test (1), how much can you answer?
  • A thorough understanding of prototypes and prototype chains in JavaScript
  • Complete understanding of EventLoop in JavaScript
  • “2W word big chapter 38 interview questions” completely clear JS this pointing to the problem

After the language

Guys, if you find this article helpful, give a like to 👍 or follow ➕ to support me.

In addition, if this article has a question, or do not understand part of the article, you can reply to me in the comment section, we come to discuss, learn together, progress together!

If you feel that the comment section does not understand, you can also add my wechat (li444186976) or QQ (3315161861) for detailed communication, the name is battlefield small bag.