精读《算法题 - 通配符匹配》
今天我们看一道 leetcode hard 难度题目：通配符匹配。
题目
给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：
'?'可以匹配任何单个字符。'*'可以匹配任意字符序列（包括空字符序列）。 判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。
示例 1：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
思考
最直观的思考是模拟匹配过程，以 s = "abc", p = "abd" 为例，匹配过程是这样的：
- "a" 匹配 "a"，通过
- "b" 匹配 "b"，通过
- "c" 不匹配 "d"，失败
只要匹配过程有任何一个字符匹配失败，则整体匹配失败。如果没有 '?' 与 '*' 号，题目则异常简单，只要一个指针按顺序扫描，扫描过程每个字符必须相等，且同时结束才算成功，否则判断失败。
加上 '?' 依然很简单，因为 '?' 号一定会消耗掉，只是它可以匹配任何字符，所以还是一个指针扫描，遇到 p 中 '?' 号时，跳过判等继续向后扫描即可。
加上 '*' 号时该题成为 hard 的第一个原因。由于 '*' 可以匹配空字符，也可以匹配任意多个字符，所以遇到 p 中 '*' 时有三种处理可能性：
- 当做没见过
'*'，直接判等，不消耗s，并匹配p的下一个字符。此时对应'p'不匹配任何字符。 - 直接消耗掉
'*'判等，同时消耗s与p。此时'*'与'?'的作用等价。 - 不消耗
'*'，但是消耗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。 - 为
'*'时：- 如果该
'*'不匹配任何字符，则可以认为这个字符不存在，pi 回退一位，所以整体能否 match 取决于 dp(si, pi-1) 的结果。 - 如果该
'*'匹配字符，则当前肯定能匹配上，但整体能否 match 取决于之前的结果，之前结果分两种： - 消耗该
'*'，则等价于 dp(si-1, pi-1) 的结果。 - 不消耗该
'*'，则等价于 dp(si-1, pi) 的结果。
- 如果该
由于所有的分支包含了所有可能性，因此上面逻辑梳理是不重不漏的。
特别的，消耗该 '*' 等价于 dp(si-1, pi-1) 的 case 可以忽略，因为已经被上述逻辑覆盖了，具体是怎么覆盖的呢？见下面的表达：
消耗该 '*' 等价于 dp(si-1, pi-1) 这个场景等价于：
- 不消耗该
'*'，等价于 dp(si-1, pi)。 - 接着该
'*'不匹配任何字符。
看到了吗，如果不消耗该 '*' 匹配字符后，接着再让其不匹配任何字符，就等价于消耗该 '*' 匹配字符！ 所以这块是一个性能优化点，看你能不能意识到，这样可以少一个逻辑分支的执行。
代码如下：
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 题了，这与面试时大部分面试者实际反应不符。
本题真正难点在于：
- 首先为了能 AC，正匹配的思路走不通，如果你不能抛下从左到右匹配字符串的成见，就没办法逼自己试试动态规划，因为动态规划是向前推导的，很多人过不去这个坎。
- 短时间内很难理解到
'*'号匹配从左向右吃，与从右向左吃最终结果是等价的，所以潜意识会觉得 dp 思路无法处理'*'号匹配规则，非得整出个dp(i+1)才能理解，这样就迟迟无法下笔了。
不得不说 p[pi] = '*' 时结果等价于 dp(si-1, pi) 是具有思维跳跃的，因为它满足 dp 利用历史结果推导的结构，同时在匹配逻辑上又确实是等价的，能否想到这一步是这道题解题的关键。
如果你在其他地方看到本题的题解，但是在 p[pi] = '*' 时等价于 dp(si-1, pi) 这一步没看懂，大概率是那个题解忽略了这个 “神之细节”，而这个 “神之细节” 却是你在做题时真正的思维卡点，请确保这一点可以在你正序思考时推导出来，而不是看了答案后觉得这个转移方程有道理，从答案反推总是轻而易举的，但解题时却需要跳跃性思维。
最后，本文的实现还留了一些优化项可以更进一步，留给阅读本文的你探索：
- dp 缓存是否可以用滚动数组优化空间消耗。
- 两层 for 循环还是比较笨拙的，在某些情况下其实可以提前终止。
- 当字符串 p 存在多个连续 * 时效果与单个 * 是一样的，可以提前简化 p 的复杂度。
讨论地址是：精读《算法 - 二叉搜索树》· Issue #337 · dt-fe/weekly
腾讯云开发者
