Skip to content

Latest commit

 

History

History
244 lines (177 loc) · 11.4 KB

283.精读《算法题 - 通配符匹配》.md

File metadata and controls

244 lines (177 loc) · 11.4 KB
Raw

今天我们看一道 leetcode hard 难度题目：通配符匹配。

题目

给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：

  • '?' 可以匹配任何单个字符。
  • '*' 可以匹配任意字符序列（包括空字符序列）。 判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

示例 1：

输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

思考

最直观的思考是模拟匹配过程，以 s = "abc", p = "abd" 为例，匹配过程是这样的：

  1. "a" 匹配 "a"，通过
  2. "b" 匹配 "b"，通过
  3. "c" 不匹配 "d"，失败

只要匹配过程有任何一个字符匹配失败，则整体匹配失败。如果没有 '?' 与 '*' 号，题目则异常简单，只要一个指针按顺序扫描，扫描过程每个字符必须相等，且同时结束才算成功，否则判断失败。

加上 '?' 依然很简单，因为 '?' 号一定会消耗掉，只是它可以匹配任何字符，所以还是一个指针扫描，遇到 p 中 '?' 号时，跳过判等继续向后扫描即可。

加上 '*' 号时该题成为 hard 的第一个原因。由于 '*' 可以匹配空字符，也可以匹配任意多个字符，所以遇到 p 中 '*' 时有三种处理可能性：

  1. 当做没见过 '*'，直接判等，不消耗 s，并匹配 p 的下一个字符。此时对应 '*' 不匹配任何字符。
  2. 直接消耗掉 '*' 判等，同时消耗 s 与 p。此时 '*' 与 '?' 的作用等价。
  3. 不消耗 '*'，但是消耗 s。此时对应 '*' 匹配多个字符而可以不消耗自己的特性。

很容易想到写一个递归的实现，代码如下：

function isMatch(s: string, p: string): boolean {
  return myIsMatch(s.split(''), p.split(''))
};

function myIsMatch(sArr: string[], pArr: string[]): boolean {
  // 如果 s p 都匹配完了，或 p 还剩任意数量的 *，都算匹配通过
  if (
    (sArr.length === 0 && pArr.length === 0) ||
    (sArr.length === 0 && pArr.every(char => char === '*'))
  ) {
    return true
  }

  // 如果任意一项长度为 0，另一项不为 0，则匹配失败
  if (
    (sArr.length === 0 && pArr.length !== 0) ||
    (sArr.length !== 0 && pArr.length === 0)
  ) {
    return false
  }

  const newSArr = [...sArr]
  const newPArr = [...pArr]
  
  const sShfit = newSArr.shift()
  const pShift = newPArr.shift()

  // 此时 sShfit、pShift 一定都存在
  switch(pShift) {
    case '?':
      // 无条件判过
      return myIsMatch(newSArr, newPArr)
    case '*':
      // 无条件判过，其中有以下几种情况
      // 消耗 *、消耗 sShfit
      // 消耗 *、不消耗 sShfit
      // 不消耗 *、消耗 sShfit

      return (
        myIsMatch(newSArr, newPArr) ||
        myIsMatch([sShfit, ...newSArr], newPArr) ||
        myIsMatch(newSArr, [pShift, ...newPArr])
      )
    default:
      if (sShfit !== pShift) {
        return false
      } else {
        return myIsMatch(newSArr, newPArr)
      }
  }
}

非常简洁清晰的代码，即判断 pShfit（p 下一个字符）的状态，根据我们分析的可能性判断匹配命中的条件，比如当 pShfit 为 '?' 时直接判定下一组字符，而为 '*' 时，三种可能性都可以判对，其余情况必须在当前字符相等时，才继续判断下一组字符。

然而上面的代码无法 AC，原因是性能不达标，无论如何优化都无法 AC，这是该题成为 hard 的第二个原因。

遇到思路正确，但遇到比较复杂的用例超时，此时 99% 的情况应该换到动态规划思路，而该题动态规划思路是比较难想到的。

动态规划思路

之所以动态规划思路难想到，是因为我们大脑的局限性造成的。因为人类最自然理解事物的方式是线性还原该场景的每一幕，对于这道题，我们自然会假设匹配是从第一个字符开始的，匹配完后进行下一个字符的匹配，直到判断失败。

但动态规划的思路是寻找 dp(i) 与 dp(i-1) 甚至 i-n 的关系，这使得直观上觉得不可能，因为想到 '*' 号的匹配可能存在不消耗 '*' 号的情况，此时向前回溯感觉就像字符串从后向前匹配了一样。但仔细想想会发现，从后向前匹配的结果与从前向后的匹配结果是相同的，因此这条路是可行的。

之所以从前向后与从后向前判断是等价的，最简单的理由是把 s 与 p 字符串倒序，此时从前向后匹配在逻辑上完全等价于倒序前的从后向前匹配。

接下来要思考的是状态转移方程，首先由于 '*' 的存在，导致 s 与 p 的游标可能不同，所以我们要定义两个游标，分别是 si、pi。

所以 dp(si, pi) 可以确定下来了。

接下来要如何转移，取决于 p[pi] 的值：

  • 为非 '?' 或 '*' 时，如果 s[si] === p[pi]，则整体能否 match 取决于 dp(si-1, pi-1) 能否 match。
    • 展开说一下，因为此时 s 与 p 字符都会消耗，所以上一个状态是 si, pi 同时减 1。
  • 为 '?' 时，不用判断当前字符是否相同，整体能否 match 取决于 dp(si-1, pi-1) 能否 match。
  • 为 '*' 时：
    1. 如果该 '*' 不匹配任何字符，则可以认为这个字符不存在，pi 回退一位，所以整体能否 match 取决于 dp(si, pi-1) 的结果。
    2. 如果该 '*' 匹配字符，则当前肯定能匹配上，但整体能否 match 取决于之前的结果，之前结果分两种：
    3. 消耗该 '*'，则等价于 dp(si-1, pi-1) 的结果。
    4. 不消耗该 '*'，则等价于 dp(si-1, pi) 的结果。

由于所有的分支包含了所有可能性，因此上面逻辑梳理是不重不漏的。

特别的，消耗该 '*' 等价于 dp(si-1, pi-1) 的 case 可以忽略，因为已经被上述逻辑覆盖了，具体是怎么覆盖的呢？见下面的表达：

消耗该 '*' 等价于 dp(si-1, pi-1) 这个场景等价于：

  1. 不消耗该 '*'，等价于 dp(si-1, pi)。
  2. 接着该 '*' 不匹配任何字符。

看到了吗，如果不消耗该 '*' 匹配字符后，接着再让其不匹配任何字符，就等价于消耗该 '*' 匹配字符！ 所以这块是一个性能优化点，看你能不能意识到，这样可以少一个逻辑分支的执行。

代码如下：

function isMatch(s: string, p: string): boolean {
  // key 为 si_pi
  const resultSet = new Set<string>()

  // 初始值
  // 俩空字符串 match
  resultSet.add('0_0')

  // 为了让 0_0 命中空字符串，在 s,p 前面补上空字符串
  s = ' ' + s
  p = ' ' + p

  for (let si = 0; si < s.length; si++) {
    for (let pi = 0; pi < p.length; pi++) {
      switch(p[pi]) {
        case '?':
          // 只要 [si-1, pi-1] match, [si, pi] 就 match
          if (resultSet.has(`${si-1}_${pi-1}`)) {
            resultSet.add(`${si}_${pi}`)
          }
          break
        case '*':
          // * 可以匹配空字符，则等价于 [si, pi-1]
          // * 可以匹配 1~oo 个字符, 如果 [si-1, pi-1] match & si > 0, 可以等价于 [si-1, pi]
          if (
            resultSet.has(`${si}_${pi-1}`) ||
            (si > 0 && resultSet.has(`${si-1}_${pi}`))
          ) {
            resultSet.add(`${si}_${pi}`)
          }
          break
        default:
          // [si-1, pi-1] match & 最后一个字符也相等, [si, pi] 就 match
          if (resultSet.has(`${si-1}_${pi-1}`) && s[si] === p[pi]) {
            resultSet.add(`${si}_${pi}`)
          }
      }
    }
  }

  return resultSet.has(`${s.length-1}_${p.length-1}`)
};

其中我们用 Set 结构很方便的定义 dp 缓存，然后给字符串前缀塞了空格，目的是方便在 si = 0, pi = 0 时收敛到 match 的情况，这样 dp 就能转起来了，否则 s[0] 和 p[0] 可能不匹配，让 dp(0, 0) 找不到一个稳定的落点（服务很到位）。

动态规划 * 号处理详解

dp 思路中，可能有些同学不好理解 p[pi] = '*' 时的推演逻辑，我们展开画个图就清楚了：

s = a b c d
p = a b c d *

如果 * 不用于匹配，则结果等价于

s = a b c d
p = a b c d

这个例子显然符合 p 可以匹配 s 的直觉。

如果 * 用于匹配，且消耗 * 比较好理解，s 与 p 各退一个字符；但不消耗 * 还是要画个图说明：

s = a b c d
p = a b c d *

'*' 匹配了 s 最后一个字符 d，但自己又不消耗，则等价于：

s = a b c
p = a b c d *

从左到右看不太好理解，但从右到左看就比较容易了，可以认为 '*' 把 s 的最后一个字符 d “吃掉了”，但自己没有被消耗。要理解到这一步，还需要理解到 '*' 从左到右与从右到左匹配都是等价的这个事实。

如果非要从左到右看，也可以解释得通：既然 '*' 已经确定要在不消耗自己的情况下把 s 最后一个 d “吃掉”，那么这个 d 写于不写是等价的，所以可以把它从末尾 “抹去”。

总结

从这道题可以看出，该题 hard 点不在于动态规划，不然理解了动态规划大家都能秒杀 hard 题了，这与面试时大部分面试者实际反应不符。

本题真正难点在于：

  1. 首先为了能 AC，正匹配的思路走不通，如果你不能抛下从左到右匹配字符串的成见，就没办法逼自己试试动态规划，因为动态规划是向前推导的，很多人过不去这个坎。
  2. 短时间内很难理解到 '*' 号匹配从左向右吃，与从右向左吃最终结果是等价的，所以潜意识会觉得 dp 思路无法处理 '*' 号匹配规则，非得整出个 dp(i+1) 才能理解，这样就迟迟无法下笔了。

不得不说 p[pi] = '*' 时结果等价于 dp(si-1, pi) 是具有思维跳跃的，因为它满足 dp 利用历史结果推导的结构，同时在匹配逻辑上又确实是等价的，能否想到这一步是这道题解题的关键。

如果你在其他地方看到本题的题解，但是在 p[pi] = '*' 时等价于 dp(si-1, pi) 这一步没看懂，大概率是那个题解忽略了这个 “神之细节”，而这个 “神之细节” 却是你在做题时真正的思维卡点，请确保这一点可以在你正序思考时推导出来，而不是看了答案后觉得这个转移方程有道理，从答案反推总是轻而易举的，但解题时却需要跳跃性思维。

最后，本文的实现还留了一些优化项可以更进一步，留给阅读本文的你探索：

  1. dp 缓存是否可以用滚动数组优化空间消耗。
  2. 两层 for 循环还是比较笨拙的，在某些情况下其实可以提前终止。
  3. 当字符串 p 存在多个连续 * 时效果与单个 * 是一样的，可以提前简化 p 的复杂度。

讨论地址是：精读《算法 - 二叉搜索树》· Issue #493 · dt-fe/weekly

如果你想参与讨论，请 点击这里，每周都有新的主题，周末或周一发布。前端精读 - 帮你筛选靠谱的内容。

关注 前端精读微信公众号

版权声明：自由转载-非商用-非衍生-保持署名（创意共享 3.0 许可证）