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

‘.’ 匹配任意单个字符

‘*’ 匹配零个或多个前面的那一个元素

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

示例 1：

输入：s = “aa”, p = “a”

输出：false

解释：”a” 无法匹配 “aa” 整个字符串。

示例 2:

输入：s = “aa”, p = “a*”

输出：true

解释：因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。

示例 3：

输入：s = “ab”, p = “.*”

输出：true

解释：”.“ 表示可匹配零个或多个（’‘）任意字符（’.’）。

提示：

  • 1 <= s.length <= 20
  • 1 <= p.length <= 20
  • s 只包含从 a-z 的小写字母。
  • p 只包含从 a-z 的小写字母，以及字符 . 和 *。
  • 保证每次出现字符 * 时，前面都匹配到有效的字符

解题思路

这条题目很难，看到了之后没有啥好的思路，能想到的就是单纯硬比较，所以就顺着这个思路来看。匹配字符串s和模板字符串p各取出一个字符s[i]和p[j]，需要看一下p[j+1]是不是”*”，

  1. p[j+1]不是”*”, 那么比较这s[i]和p[j]是否一样,当然这里的一样包含p[j]是”.”的意思，因为”.”是万能字符，一样的话那么比较s[i+1]和p[j+1]，不一样返回false

  2. p[j+1]是*，那么有两种情况

    a. 看一下p[j+2]和s[i]是不是一样的，有可能这个”*”代表0次p[j]

    b. 看一下s[i]和p[j]是不是一样的，如果一样的看一下s[i+1]和p[j]是不是一样的，可能这个”*”代表多次

这样直到p字符都被检查完，如果此时s的字符还没被匹配完，那么返回false，如果s的字符串在这之前就被检查完的话，也返回false，其余就是完全覆盖。
这里我们可以看到检测s[n]和p[x]的逻辑都是一样的，那么就可以抽出来做成递归。

递归法代码

var isMatch = function(s, p) {
  //模式字符串为0的时候，如果匹配字符串还有值那么返回false
  if (p.length <= 0) return s.length <= 0
  
  const match = s.length > 0 && (s[0] === p[0] || p[0] === '.')
  
  if (p.length > 1 && p[1] === '*') {
      //跳过模式字符串后面跟着*的字符进行匹配 或者 当前字符匹配那么看接下来的字符是不是匹配
      return isMatch(s, p.substring(2)) || (match && isMatch(s.substring(1), p))
  }else {
      // p长度为1时，需要字符匹配，且同时匹配字符串已经被匹配完
      return match && isMatch(s.substring(1), p.substring(1))
  }
}

逻辑推演

例子1： s = “aa”，p = “a”

  1. 取出s[0] 和 p[0]，查看p[1]是否是”*”，p长度不够，那么比较s[0]和p[0]是否一致，一致那么比较后面内容
  2. 取出s[1] 和 p[1]，因为p长度不够，这时检查s字符串有没有匹配完，发现没有，返回false

例子2： s = “aab”，p = “cab”

  1. 取出s[0]和p[0]，查看p[1]是否是”*”，发现是的，那么进行两种特殊逻辑判断: 看p[2]和s[0]是否一致 || s[0]和p[0]是否一致且s[1]和p[0]是否一致
    1. 看p[2]和s[0]是否一致，需要看p[3]是否是”*”，发现是的，那么进行两种特殊逻辑判断: 看p[4]和s[0]是否一致 || p[2]和s[0]是否一致且s[1]和p[2]是否一致
      1. 看p[4]和s[0]是否一致，需要看p[5]是否是”*”，发现不是，且p[4]和s[0]不一致
      2. 看p[2]和s[0]是否一致，一致的，s[1]和p[2]是否一致，需要看p[3]是否是”*”，发现是的，那么进行两种特殊逻辑判断: 看p[4]和s[1]是否一致 || p[2]和s[1]是否一致且s[2]和p[2]是否一致
        1. 看p[4]和s[1]是否一致，需要看p[5]是否是”*”，发现不是，且p[4]和s[1]不一致
        2. 看p[2]和s[1]是否一致，一致的，s[2]和p[2]是否一致，需要看p[3]是否是”*”，发现是的，那么进行两种特殊逻辑判断: 看p[4]和s[2]是否一致 || p[2]和s[2]是否一致且s[3]和p[2]是否一致
          1. 看p[4]和s[2]是否一致，需要看p[5]是否是”*”，发现不是，且p[4]和s[2]不一致
          2. 看p[2]和s[2]是否一致，一致的，看s[3]和p[2]是否一致，需要看p[3]是否是”*”，发现是的，那么进行两种特殊逻辑判断: 看p[4]和s[3]是否一致 || p[2]和s[3]是否一致且s[4]和p[2]是否一致
            1. 看p[4]和s[3]是否一致，需要看p[5]是否是”*”，发现不是，那么看p[4]和s[3]是否一致，一致，p和s都进行到了尾部，向上回溯，满足条件覆盖
            2. 看p[2]和s[3]是否一致，不一致
    2. 看s[0]和p[0]是否一致且s[1]和p[0]是否一致，类似的推论….

看上去还行，但是上传答案一看，击败了2%的人，为什么会这样，看上面的逻辑推演，就能看出来，其中有很多遍历都重复了

动态规划的方式

动态规划的方式就是将一个大问题拆分成小问题，并记录下每个小问题的过程结果，最后多个小问题都解决了，那么大问题也解决了。

我们使用s[i:]来代表s从i到最后的子串，用match(i, j)来表示s[i:]和p[j:]之间的匹配关系，返回true就是匹配上了，false就是没匹配上。

match(i, j)这个问题解决的关键在于p[j+1]是否是”*”

  • 不是的话，只需要比较s[i]和p[j]是否匹配，不匹配就返回false，匹配的话，问题转换为看后一位的两个字符是否匹配了，即match(i+1, j+1)
  • 是的话，就分为两种子情况:
    • 中间的*代表0次，问题转换为看”*“号后面字符和s[i]是否匹配，即match(i, j+2)
    • 看s[i]和p[j]是否匹配，不匹配返回false，匹配的话，这个*就表示多次，看s后一个字符是不是也跟这个字符相同，即match(i+1, j)

同时记录下这些中间过程的结果，以便复用

c * a * b
a T T F
a T F
b T

动态规划代码

var isMatch = function(s, p) {
    const result = []
    for (let i = 0; i < s.length + 1; i++) {
        result.push(new Array(p.length + 1).fill(null))
    }

    function match(i, j) {
        if (result[i][j] !== null) {
            return result[i][j]
        }
        let ans = false
        if (j >= p.length) {
            ans = i >= s.length
        }else {
            const curMatch = i < s.length && (s[i] === p[j] || p[j] === '.')
            if (j+1 >= p.length || p[j+1] !== '*') {
                ans = curMatch && match(i+1, j+1)
            }else {
                ans = match(i, j+2) || (curMatch && match(i+1,j))
            }
        }
        result[i][j] = ans
        return ans
    }

    return match(0, 0)
};

代码推演

求match(0,0): i = 0; j = 0; curMatch = false;
p[1] == * -> match(0,0) = match(0,2) || false && match(1,0)
转化为求子问题match(0,2)和match(1,0)
求match(0,2): i = 0; j = 2; curMatch = true;
p[1] == * -> match(0,2) = match(0,4) || true && match(1,2)
求match(0,4): i = 0; j = 4; curMatch = false;
j + 1 == 5 >= p.length() -> match(0,4) = curMatch = false;
match(0,4) = false;
回溯到第五步，求match(1,2): i = 1; j = 2; curMatch = true;
p[3] == * -> match(1,2) = match(1,4) || true && match(2,2)
求match(1,4): i = 1; j = 4; curMatch = false;
j + 1 == 5 >= p.length() -> match(1,4) = curMatch = false;
match(1,4) = false;
回溯到第10步，求match(2,2): i = 2; j = 2; curMatch = false;
p[3] == * -> match(2,2) = match(2,4) || false && match(3,2)
求match(2,4): i = 2; j = 4; curMatch = true;
j + 1 == 5 >= p.length() -> match(2,4) = curMatch = true;
match(2,4) = true;
回溯到第15步。
match(2,2) = true;
回溯到第10步。
match(1,2) = true;
回溯到第5步。
match(0,2) = true;
回溯到第2步。
match(0,0) = true;
问题解决