This is my second article about getting started.

1. Title Description

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

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

By matching, you want to cover the entire string S, not parts of the string.

Example 1:

Input: s = "aa" p = "a" Output: false Description: "A" cannot match the entire string "aa".Copy the code

Example 2:

Input: s = "aa" p = "a*" Output: true Thus, the string "aa" can be treated as 'a' repeated once.Copy the code

Example 3:

Input: s = "ab" p = ".*" Output: true Description: ".*" can match zero or more ('*') characters ('.').Copy the code

Thought analysis

The matching in the title is a “step by step matching” process: we take one character or a combination of “character + asterisk” from the string P and match it in S at a time. For a character in P, it can only match one character in S, and the matching method is unique. However, for the combination of character + asterisk in P, it can match any natural number of characters in S and is not unique. So we can consider using dynamic programming to enumerate matching schemes.

  • This problem examines how to use the idea of dynamic programming to find the optimal solution to the problem. Dp [I][j] can indicate whether the first I of S can be matched by the first j of P. First of all, the problem is how to solve the problem of dp[I][j], plus known s[I], p[j].

  • The first difficult point to figure out: how to distinguish between the two discussion cases of * first given *, understand the meaning of * is to match zero or more of the preceding element, so we should consider the element before him p[J-1]. * if the string matches s[I], the string matches 0 times. * if the string matches s[I], the string matches 0 times.

  • The second hard point to figure out: How do YOU tell if the front matches

    Dp [I] [j] = dp [I - 1) [j] / / multiple characters match the or dp [I] [j] = dp [I] [1] / / a single character match or dp [I] [j] = dp [I] [2] / / there is no matching conditionsCopy the code

  • The next idea is to achieve the code, because the front-end industry itself is more familiar with JavaScript so use JS code to achieve

AC code

const isMatch = (s, p) => { if (s == null || p == null) return false; const sLen = s.length, pLen = p.length; const dp = new Array(sLen + 1); for (let i = 0; i < dp.length; i++) { dp[i] = new Array(pLen + 1).fill(false); // base case dp[0][0] = true; for (let j = 1; j < pLen + 1; j++) { if (p[j - 1] == "*") dp[0][j] = dp[0][j - 2]; } // iterate for (let I = 1; i < sLen + 1; i++) { for (let j = 1; j < pLen + 1; j++) { if (s[i - 1] == p[j - 1] || p[j - 1] == ".") { dp[i][j] = dp[i - 1][j - 1]; } else if (p[j - 1] == "*") { if (s[i - 1] == p[j - 2] || p[j - 2] == ".") { dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2]  || dp[i - 1][j]; } else { dp[i][j] = dp[i][j - 2]; } } } } return dp[sLen][pLen]; // Whether long sLen s string matches long pLen p string};Copy the code

Four,

Dp [I -1][J -1], plus known s[I], p[j], To think about the problem is how to solve dp[I][J] naturally thought of dynamic programming algorithm implementation.