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

今天我们看一道 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. 直接消耗掉 '*' 判等,同时消耗 sp。此时 '*''?' 的作用等价。
  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 许可证