给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

  • ‘.’ 匹配任意单个字符
  • ‘*’ 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。

思路

  1. 动态规划，维护 dp[][]，dp[sLength][pLength] 表示 s 的前 sLength 个字符和 p 的前 pLength 个字符匹配情况
  2. 初始值 dp[0][0] = true
  3. 重点处理特殊字符 . 和 *
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
var isMatch = function (s, p) {
  const dp = []
  for (let i = 0; i <= s.length; ++i) {
    dp.push(new Array(p.length + 1).fill(false))
  }
  dp[0][0] = true
  // dp[0][*] 的初始值与 p 字符串中 * 有关，a*b* 意味着 dp[0][2] 和 dp[0][4] 为 true
  for (let j = 1; j < p.length; ++j) {
    if (p[j] === '*' && dp[0][j - 1]) {
      dp[0][j + 1] = true
    }
  }
  for (let i = 0; i < s.length; ++i) {
    for (let j = 0; j < p.length; ++j) {
      if (s[i] === p[j] || p[j] === '.') {
        dp[i + 1][j + 1] = dp[i][j]
      } else if (p[j] === '*') {
        if (p[j - 1] !== s[i] && p[j - 1] !== '.') {
          // s[i] 与 p[j - 1] 不匹配时，可将 * 视为 {0}
          dp[i + 1][j + 1] = dp[i + 1][j - 1]
        } else {
          // s[i] 与 p[j - 1] 匹配时，可将 * 视为 {0}，{1}, {2}
          dp[i + 1][j + 1] = dp[i + 1][j - 1] || dp[i + 1][j] || dp[i][j + 1]
        }
      }
    }
  }
  return dp[s.length][p.length]
}