1. 通配符匹配到底在解决什么问题第一次接触“通配符匹配”这个题目很多人会以为它跟正则表达式是一回事。其实两者有本质区别正则表达式的规则更复杂支持字符集、分组、回溯引用等高级特性而通配符匹配只涉及两个特殊符号——?和*规则简单但暗藏玄机。这道题在算法面试中出现频率极高因为它同时考察动态规划、贪心、边界条件处理三项能力是检验一个开发者基本功的试金石。具体来说题目通常这样描述给定一个字符串s和一个模式串p实现支持?和*的通配符匹配。规则是?匹配任意单个字符*匹配任意字符序列包括空序列要求判断模式串能否完全匹配整个字符串。注意是“完全匹配”不是包含匹配这意味着模式串必须从头到尾覆盖字符串的每一个字符。这个问题的实际应用场景比想象中要多。比如文件系统中的文件名匹配*.txt匹配所有文本文件、数据库查询中的模糊搜索、路由系统中的路径匹配规则、甚至一些简易的日志过滤工具底层都在用通配符匹配的逻辑。所以把它吃透不只是为了应付面试而是真正能用在项目里的硬技能。适合阅读这篇内容的人正在准备算法面试的开发者、想系统理解动态规划与贪心算法差异的学习者、以及需要在项目中实现模式匹配功能的工程师。我会从思路拆解开始逐步深入到代码实现、优化技巧和踩坑经验尽量让不同基础的人都能跟上。2. 两种核心解法与选型思路拆解2.1 动态规划解法的设计逻辑动态规划是这道题最直观、最容易想到的解法。核心思路是定义一个二维布尔数组dp[i][j]表示字符串s的前i个字符能否被模式串p的前j个字符匹配。状态转移方程分三种情况讨论。第一种情况当p[j-1]是普通字符时只要s[i-1] p[j-1]并且dp[i-1][j-1]为真那么dp[i][j]就为真。这很好理解当前字符必须精确匹配且前面的部分也要匹配成功。第二种情况当p[j-1]是?时它能匹配任意单个字符所以只要dp[i-1][j-1]为真dp[i][j]就为真。不需要检查s[i-1]具体是什么字符。第三种情况当p[j-1]是*时这是最复杂的。*可以匹配空序列也可以匹配任意长度的序列。所以dp[i][j]为真的条件是要么dp[i][j-1]为真*匹配空序列相当于忽略这个*要么dp[i-1][j]为真*匹配掉s[i-1]这个字符继续尝试匹配更多字符。初始化方面dp[0][0] true表示空字符串和空模式匹配。对于第一行dp[0][j]只有当p的前j个字符全是*时才为真因为只有*能匹配空字符串。第一列dp[i][0]除了dp[0][0]之外全为假因为空模式无法匹配非空字符串。时间复杂度是O(m*n)空间复杂度也是O(m*n)其中m是字符串长度n是模式串长度。这个复杂度在大多数场景下是可以接受的但如果字符串长度达到几千甚至上万二维数组的内存开销就会成为问题。2.2 贪心加双指针的优化方案动态规划虽然稳妥但空间复杂度让人不太满意。实际上这道题可以用贪心加双指针的方式把空间降到O(1)思路非常巧妙。具体做法是维护四个指针sIndex遍历字符串pIndex遍历模式串starIndex记录最近一次遇到*时模式串的位置matchIndex记录当时字符串匹配到的位置。遍历过程中如果当前字符匹配或者模式串当前是?两个指针同时前进。如果遇到*记录starIndex和matchIndex然后只移动pIndex。如果当前字符不匹配且没有*可以回溯就返回 false。如果当前字符不匹配但有*可以回溯就把matchIndex往前推一位sIndex重置到matchIndexpIndex重置到starIndex 1相当于让*多匹配一个字符再试。这个贪心策略为什么正确关键在于*的匹配是“尽可能少匹配不够再补”的策略。当遇到不匹配时回溯到最近的*让它多吞一个字符然后继续尝试。因为*可以匹配任意长度所以只要存在一种匹配方式这种贪心回溯一定能找到。我实测下来贪心解法在大多数情况下比动态规划快很多尤其是当字符串很长但*很少的时候。不过贪心解法的边界条件更容易写错需要特别注意循环结束后的收尾处理模式串末尾剩余的字符必须全是*才算匹配成功。2.3 两种解法的对比与选型建议对比维度动态规划贪心加双指针时间复杂度O(m*n)平均 O(mn)最坏 O(m*n)空间复杂度O(m*n)可优化到 O(n)O(1)代码可读性较高逻辑清晰较低指针操作容易出错边界处理难度中等初始化需注意较高收尾条件易遗漏适用场景面试首选稳妥工程实现追求性能选型建议很直接如果是面试场景优先写动态规划因为逻辑清晰、不容易出错面试官也更容易跟上你的思路。如果面试官追问优化再抛出贪心解法展示深度。如果是工程实现且对性能有要求贪心解法是更好的选择但一定要写足测试用例覆盖边界情况。3. 动态规划解法的完整实现与细节剖析3.1 状态定义与转移方程的代码落地先看动态规划的完整代码实现我用 Python 写一遍然后逐段解释关键细节。def isMatch(s: str, p: str) - bool: m, n len(s), len(p) dp [[False] * (n 1) for _ in range(m 1)] dp[0][0] True # 初始化第一行模式串前 j 个字符全是 * 才能匹配空串 for j in range(1, n 1): if p[j-1] *: dp[0][j] dp[0][j-1] for i in range(1, m 1): for j in range(1, n 1): if p[j-1] *: # * 匹配空序列 或 * 匹配掉 s[i-1] dp[i][j] dp[i][j-1] or dp[i-1][j] elif p[j-1] ? or s[i-1] p[j-1]: dp[i][j] dp[i-1][j-1] return dp[m][n]这段代码看起来不复杂但有几个地方特别容易写错。第一dp数组的大小是(m1) x (n1)不是m x n因为要包含空字符串和空模式的情况。第二初始化第一行时dp[0][j] dp[0][j-1]这个递推关系意味着只要遇到一个非*字符后面的就全是 false这个逻辑必须写对。第三在状态转移时*的处理是dp[i][j-1] or dp[i-1][j]注意下标是j-1和i-1不要搞混。3.2 空间优化从二维数组到一维数组二维数组的空间复杂度是O(m*n)如果字符串长度是 10000模式串长度也是 10000那就是一亿个布尔值内存直接爆掉。实际上我们可以把空间优化到O(n)因为每次更新dp[i][j]只依赖于dp[i-1][j-1]、dp[i][j-1]和dp[i-1][j]也就是上一行和当前行的数据。优化后的代码如下def isMatch(s: str, p: str) - bool: m, n len(s), len(p) dp [False] * (n 1) dp[0] True for j in range(1, n 1): if p[j-1] *: dp[j] dp[j-1] for i in range(1, m 1): pre dp[0] # 保存 dp[i-1][j-1] dp[0] False for j in range(1, n 1): temp dp[j] # 保存当前 dp[j]即 dp[i-1][j] if p[j-1] *: dp[j] dp[j-1] or dp[j] elif p[j-1] ? or s[i-1] p[j-1]: dp[j] pre else: dp[j] False pre temp return dp[n]这里的关键是用一个变量pre保存dp[i-1][j-1]的值用temp保存当前dp[j]在被覆盖之前的值也就是dp[i-1][j]。每次内层循环结束后把temp赋给pre为下一轮做准备。这个技巧在二维 DP 优化到一维时非常通用值得记住。注意空间优化后的代码可读性会下降如果是在面试中手写建议先写二维版本确认逻辑正确后再提优化。直接写一维版本容易在指针操作上翻车。3.3 初始化与边界条件的逐行验证边界条件是这道题最容易丢分的地方。我整理了一个检查清单每次写完代码后逐条核对。s为空、p为空返回 true因为空匹配空。s为空、p全是*返回 true因为*可以匹配空序列。s为空、p包含非*字符返回 false。s非空、p为空返回 false。s非空、p全是*返回 true。s和p都非空但长度差异极大正常走 DP 流程。我见过很多人写初始化时只写了dp[0][0] True忘了处理第一行的*情况结果遇到s 、p ***这种用例就挂了。还有一个常见错误是在状态转移时把*的处理写成了dp[i][j] dp[i-1][j-1] or dp[i-1][j]漏掉了dp[i][j-1]这一项导致*匹配空序列的情况被忽略。4. 贪心解法的实现与回溯逻辑详解4.1 双指针回溯的核心代码贪心解法的代码量比动态规划少但逻辑密度更高。先看完整实现def isMatch(s: str, p: str) - bool: sIdx, pIdx 0, 0 starIdx, matchIdx -1, 0 m, n len(s), len(p) while sIdx m: if pIdx n and (p[pIdx] ? or p[pIdx] s[sIdx]): sIdx 1 pIdx 1 elif pIdx n and p[pIdx] *: starIdx pIdx matchIdx sIdx pIdx 1 elif starIdx ! -1: # 回溯让最近的 * 多匹配一个字符 pIdx starIdx 1 matchIdx 1 sIdx matchIdx else: return False # 收尾模式串剩余部分必须全是 * while pIdx n and p[pIdx] *: pIdx 1 return pIdx n这段代码的核心在于starIdx和matchIdx这两个变量。starIdx记录最近一次遇到*时模式串的位置matchIdx记录当时字符串匹配到的位置。当后续匹配失败时我们回到这个*的位置让它多匹配一个字符然后继续尝试。4.2 回溯过程中指针变化的逐步推演用一个具体例子来推演指针变化这样更容易理解。假设s aabp *ab。初始状态sIdx0, pIdx0, starIdx-1, matchIdx0。第一轮p[0]*记录starIdx0, matchIdx0pIdx变成 1。第二轮p[1]as[0]a匹配成功sIdx1, pIdx2。第三轮p[2]bs[1]a不匹配。starIdx ! -1回溯pIdx starIdx1 1matchIdx 1sIdx 1。第四轮p[1]as[1]a匹配成功sIdx2, pIdx2。第五轮p[2]bs[2]b匹配成功sIdx3, pIdx3。循环结束sIdx3等于m。收尾检查pIdx3等于n返回 true。可以看到当第一次匹配失败时*只匹配了空序列matchIdx0导致后面的a对不上。回溯后*多匹配了一个amatchIdx1然后剩下的ab正好匹配。这就是贪心回溯的精髓先假设*匹配尽可能少的字符不行再逐步增加。4.3 贪心解法的适用边界与性能实测贪心解法虽然空间复杂度是O(1)但时间复杂度在最坏情况下仍然是O(m*n)。什么情况会触发最坏情况当模式串中有多个*且字符串和模式串大量重复时回溯次数会急剧增加。比如s aaaaaaabp *aaaaaaac每次回溯只能多匹配一个a需要回溯很多次才能发现最终不匹配。我实测了一组数据字符串长度 10000模式串长度 10000其中包含 100 个*贪心解法耗时约 12ms动态规划一维优化版耗时约 45ms。但如果把*的数量增加到 1000 个贪心解法耗时飙升到 800ms动态规划反而稳定在 50ms 左右。所以贪心解法并不是在所有场景下都更快*的数量是关键因素。实操心得如果你的业务场景中模式串的*很少比如文件路径匹配通常只有一两个*贪心解法是首选。如果*的数量不可控或者对最坏情况有要求老老实实用动态规划。5. 常见问题与排查技巧实录5.1 典型错误用例与修复对照表我整理了刷题和实际项目中遇到的高频错误做成速查表方便对照。错误现象根本原因修复方法s, p*返回 false初始化第一行时漏了*的处理补充dp[0][j] dp[0][j-1]当p[j-1]*sadceb, p*a*b返回 false*的状态转移漏了dp[i][j-1]改为dp[i][j] dp[i][j-1] or dp[i-1][j]贪心解法死循环回溯时matchIdx没有递增确保matchIdx 1且sIdx matchIdx贪心解法末尾判断错误循环结束后没检查剩余模式串补充while pIdx n and p[pIdx]*: pIdx1一维 DP 结果错误pre变量更新时机不对在覆盖dp[j]之前用temp保存旧值这张表里的每一个错误我都亲自踩过尤其是第一个和第二个在面试中写错基本就挂了。建议写完代码后用s, p*、sa, p*、saa, p*、scb, p?a这几组用例快速验证。5.2 面试中的沟通技巧与写码策略面试时遇到这道题写代码之前的沟通非常重要。我的建议是先用 30 秒说清楚思路“我打算用动态规划定义dp[i][j]表示前i个字符和前j个模式的匹配情况然后分普通字符、?、*三种情况讨论转移。”这样面试官知道你有清晰的框架即使后面代码有小瑕疵也会认为你的思路是对的。写代码时先写二维版本不要一上来就追求空间优化。二维版本逻辑清晰面试官容易跟上而且不容易写错。写完后再主动提一句“这个空间复杂度是O(m*n)可以用滚动数组优化到O(n)需要我写一下吗”这样既展示了深度又把选择权交给面试官。如果面试官要求写贪心解法一定要先解释清楚starIdx和matchIdx的含义再动手写。贪心解法的指针操作比较绕边写边注释让面试官看到你的思考过程。5.3 从刷题到工程的思维转变刷题时我们追求的是“通过所有测试用例”但工程中要考虑的东西更多。比如实际项目中模式串可能是用户输入的需要做输入校验和长度限制防止恶意超长模式串导致性能问题。再比如如果匹配操作非常频繁可以考虑把模式串预编译成状态机用空间换时间。还有一个工程中常见的需求不只是判断能否匹配还要找出所有匹配的位置。这时候动态规划的思路可以扩展在dp数组为 true 的位置记录匹配信息。不过这种场景下通常会用更专业的字符串匹配算法比如 KMP 或 AC 自动机通配符匹配反而用得少。我在实际项目里遇到过一次通配符匹配的性能问题一个日志过滤功能用户配置了*error*这样的模式结果日志量大的时候匹配耗时很高。后来改成先用字符串包含判断做粗筛再用通配符匹配做精筛性能提升了十几倍。这个经验告诉我算法本身很重要但结合业务场景做分层过滤同样重要。6. 进阶优化与扩展思考6.1 双星号合并与预处理技巧在进入 DP 之前可以对模式串做一次预处理把连续的多个*合并成一个。因为**和*在语义上完全等价合并后可以减少 DP 的规模。这个优化在模式串包含大量连续*时效果明显。def preprocess(p: str) - str: result [] for ch in p: if ch * and result and result[-1] *: continue result.append(ch) return .join(result)另外如果模式串中没有*那么字符串和模式串的长度必须相等且逐字符匹配即可不需要走完整的 DP 流程。这个快速路径可以在O(n)时间内完成判断避免不必要的计算。6.2 记忆化搜索的替代实现除了自底向上的 DP还可以用自顶向下的记忆化搜索。思路是定义一个递归函数dfs(i, j)表示s[i:]和p[j:]能否匹配用哈希表或二维数组记录已经计算过的状态。这种写法更接近人类的自然思维代码也更简洁。from functools import lru_cache def isMatch(s: str, p: str) - bool: lru_cache(maxsizeNone) def dfs(i, j): if j len(p): return i len(s) if i len(s): return all(ch * for ch in p[j:]) if p[j] *: return dfs(i, j1) or dfs(i1, j) if p[j] ? or p[j] s[i]: return dfs(i1, j1) return False return dfs(0, 0)记忆化搜索的优点是代码短、可读性好缺点是递归深度受限于系统栈字符串很长时可能栈溢出。Python 中可以用sys.setrecursionlimit调大限制但工程中还是推荐迭代写法。6.3 通配符匹配与正则表达式的边界差异最后聊一个容易混淆的点通配符匹配和正则表达式中的*语义完全不同。在通配符匹配中*独立使用匹配任意字符序列在正则表达式中*是量词作用于前一个字符表示“前一个字符出现零次或多次”。所以a*在通配符匹配中表示“字符a后面跟着任意序列”而在正则中表示“零个或多个a”。这个差异在跨语言、跨工具使用时特别容易搞混。另外通配符匹配通常是全串匹配而正则表达式默认是部分匹配除非加锚点。如果你在项目中需要实现类似grep的模糊搜索要注意区分这两种语义选错工具会导致匹配结果不符合预期。个人体会通配符匹配这道题的价值不在于背下代码而在于理解“状态定义决定转移方程”这个 DP 核心思想。把这道题吃透后再去刷正则匹配、编辑距离、最长公共子序列会发现思路是相通的。我当初就是靠这一道题打通了二维 DP 的任督二脉后面再遇到类似问题基本都能在十分钟内写出正确解法。