算法刻意练习-LeetCode实战30-通配符匹配C——完结篇30天30道题LeetCode实战系列到今天这篇正好收官。选了通配符匹配作为完结篇是因为这道题几乎涵盖了前面29天反复锤炼的所有基本功状态定义、边界处理、递归转迭代、空间复杂度优化、逻辑分支的严谨性。可以说它不是最难的题却是最值得拿来当毕业考的一道题。这篇文章不适合完全没有接触过动态规划的人直接硬啃但你只要有基本的DP概念跟着我把状态一步步画出来代码敲一遍再对照后面的坑点清单自查一遍就一定能彻底吃透。我前后用两种解法都实现了会重点讲清楚它们各自的思考路径和适用场景最后还会整理这30天刻意练习里最实用的方法沉淀。1. 为什么完结篇选通配符匹配1.1 这道题的题眼在哪里通配符匹配的题目描述很精简给定一个字符串s和一个模式串p实现一个支持两个特殊字符的匹配——?可以匹配任意单个字符*可以匹配任意长度的字符串包括空串问p是否能覆盖s。表面上看就是一次字符串遍历但真正的难点全在的处理上。它不像?那样只影响当前一个位置的选择一个星号可以吞掉s中任意长度的字符这意味着你哪怕已经匹配到一半遇到时必须停下来做一次“存档”后续如果走不通还要回来换一条路继续试。这种带状态回退的匹配模型天然就是动态规划的主场。我当初第一次做这道题的时候先试着用DFS加记忆化硬解结果状态转移没理清边界条件一堆跑出来错得稀里哗啦。后来老老实实画DP表格重写了一遍才算真正理解这个问题的结构。用事后的眼光看这道题就是在考你“能不能把一个带回溯的暴力过程抽象成一张可以逐格递推的表”。另一个容易忽略的点是空串和空模式。s为空、p为空这类输入看起来简单其实是测试DP数组初始化是否正确的关键用例很多人的代码挂在“s为空但p里全是星号”这种不起眼的例子上。1.2 这套题单的一贯思路先暴力后优化30天前我定这套刻意练习计划的时候就给自己定了一条规矩每道题至少做两遍第一遍用最直觉的方法拿到AC第二遍再想能不能优化时间和空间。通配符匹配恰好完美践行了这条规矩。第一遍用动态规划时间复杂度O(mn)空间复杂度O(mn)思路直白状态转移表画出来基本就写出来了。第二遍用双指针贪心空间降到O(1)代码更短但逻辑分支更绕对*的回溯处理要求极高。这两版代码放在一起对比你就看得到“同样的功能不同的权衡”到底是什么感觉。这个思路也延续了整个系列的核心主题算法能力不是背题而是学会在约束条件下做权衡。如果你刷题只求AC不看复杂度那练习效果至少打了一半折扣。2. 通配符匹配的两套核心方案2.1 暴力回溯为什么不可取不急着上DP先聊聊最直接的直觉解法同时遍历s和p遇到普通字符就比对?算匹配任意一个遇到就让它尽量少地匹配字符匹配失败再让多吞一个字符重试。这个思路是对的但写成纯递归的话时间复杂度最坏能到指数级。指数级慢在哪个环节在于一个星号可以多次回溯每次回溯都要重新从星号后面那个位置往下匹配。比如模式串里连续多个星号或者星号之间还有普通字符需要反复尝试路径数量会爆炸式增长。LeetCode的压测用例就是为了把这种暴力解打爆而设计的我在本地跑一组极端输入时暴力递归直接被拖到秒级。所以暴力回溯可以帮你理清“匹配到底是怎么回事”但不能作为最终提交方案。这也是我把DP放在首选的原因把重复的递归计算用表格缓存起来用空间换时间一步到位。2.2 动态规划的状态定义与转移方程DP的第一步是定义状态。我习惯把每个子问题写成一句话用 dp[i][j] 表示“s的前i个字符能否被p的前j个字符匹配”能就是true不能就是false。base case比较关键dp[0][0]表示两个都空必然是true如果s为空但p非空那p必须全是星号才能匹配空串所以dp[0][j] dp[0][j-1] p[j-1]*。反过来如果p为空但s非空必然全部是false这一行默认初始化成false就行。状态转移分三种情况如果p[j-1]是普通字符或者?当前位必须匹配上并且前面也要匹配上所以 dp[i][j] dp[i-1][j-1] (s[i-1]p[j-1] || p[j-1]?)如果p[j-1]是*这个星号有两种用法匹配空串即 dp[i][j-1]或者匹配s[i-1]这个字符即 dp[i-1][j]。两者只要有一个为true就行所以 dp[i][j] dp[i][j-1] || dp[i-1][j]第二种情况特别值得多说一句。星号匹配空串就是把星号跳过所以看“s前i个字符和p前j-1个字符”的结果星号匹配至少一个字符时相当于“s前i-1个字符已经被p前j个字符匹配好了”再用当前这个星号多吞掉s的第i个字符。这个转移是整张表格递推的灵魂我建议你在草稿纸上对着一个具体例子画一遍表格体会会很深。2.3 双指针贪心把空间压到O(1)DP写完AC之后我开始琢磨这题能不能用更少空间。DP的O(m*n)空间在字符串很长时多少有点心疼琢磨出一个基于回溯的双指针解法。核心思路是用i遍历s用j遍历p维护两个额外的原子变量star和s_tmp。每次j指向*时记录starj星号的位置和s_tmpi当时s走到哪然后j继续尝试让星号先匹配空串。后面如果不匹配了就回到star处让这个星号多吞一个字符即s_tmpis_tmpjstar1重新往后走。这个方案之所以省空间是因为它不需要记录整张DP表只记住“最近一个星号在哪”和“最近一次尝试匹配到s的哪个位置”靠反复回溯去穷举星号匹配长度。最坏情况下时间复杂度也是O(m*n)但平均表现很好而且空间O(1)。要注意几个细节。遍历结束后如果p还有剩余剩下部分必须全是星号才能返回true否则匹配失败。另外如果s还没走完但p已经用完了并且没有星号可以回溯就直接false。我第一次写双指针就漏了“p剩余全是星号”这个检查结果漏过了好几个用例。2.4 两种方案的适用场景对比方案时间复杂度空间复杂度代码长度逻辑复杂度适合场景动态规划O(m*n)O(m*n)较长中等递推清晰追求稳定AC、方便讲清楚原理双指针贪心O(m*n)最坏O(1)较短较高分支多空间受限、比赛炫技面试里我更推荐先讲DP因为状态转移方程的推导过程就是你的思路展示面试官容易follow。等DP讲完可以补一句“这题还能优化到O(1)空间”再顺势讲双指针这样既展示了基础功又体现了优化的sense。3. C实现细节与性能对比3.1 动态规划代码的写法和内存优化C写DP时有一个明显的性能优势vector的随机访问非常快即便开了二维数组也不会出现明显的性能瓶颈。不过我更推荐直接用一维数组滚动更新把空间从O(m*n)降到O(m)。滚动数组的原理很简单dp[i][j]只依赖dp[i-1][j-1]、dp[i][j-1]、dp[i-1][j]这些相邻格所以可以只保留上一行和当前行。再进一步如果我们在内层循环里从后往前更新甚至可以只用一个一维数组完成整张表的递推这就是背包问题里经典的“逆序更新”技巧。这里有个容易出错的地方dp[i-1][j-1]在滚动数组里怎么安全取到如果只用一个一维数组dp[j-1]在更新dp[j]时已经是当前行的值了严格来说存的是dp[i][j-1]不是dp[i-1][j-1]。所以要么开两个一维数组交替用要么单独用一个变量记住上一格左上方的值。我自己实测下来开两个一维数组的写法更不容易错代码也就多两行。下面是我实测通过的核心代码注释标得比较细class Solution { public: bool isMatch(string s, string p) { int m s.size(), n p.size(); // 滚动数组prev对应dp[i-1]行cur对应dp[i]行 vectorbool prev(n 1, false), cur(n 1, false); prev[0] true; // dp[0][0] true两个都是空串 for (int j 1; j n; j) { if (p[j - 1] *) prev[j] prev[j - 1]; // s为空时p只有全是星号才能匹配 } for (int i 1; i m; i) { cur[0] false; // p为空但s非空必然false for (int j 1; j n; j) { if (p[j - 1] *) { // 星号匹配空串或者匹配s[i-1] cur[j] cur[j - 1] || prev[j]; } else { // 当前字符必须相等或者p当前字符是? cur[j] prev[j - 1] (s[i - 1] p[j - 1] || p[j - 1] ?); } } swap(prev, cur); } return prev[n]; } };这版的边界处理就是针对“s为空、p为星号”的场景设计的实测能无压力通过全部用例。滚动数组对性能的提升在超长输入上尤其明显。3.2 双指针贪心的完整实现双指针的代码量短但里面的逻辑分支不仔细想清楚非常容易写错。我贴的这版是我反复调试过、加了详细注释的版本每个分支为什么存在、什么时候触发回溯我都写在注释里了。class Solution { public: bool isMatch(string s, string p) { int i 0, j 0; // i遍历sj遍历p int star -1, s_tmp -1; // 最近星号的位置以及它匹配s的进度 while (i s.size()) { if (j p.size() (p[j] ? || s[i] p[j])) { // 普通匹配当前字符相等或p是? i; j; } else if (j p.size() p[j] *) { // 遇到星号先让它匹配空串存档 star j; s_tmp i; j; } else if (star ! -1) { // 走到这里说明当前字符匹配失败且之前有星号可回溯 // 让星号多吞一个字符然后从星号后面继续匹配 s_tmp; i s_tmp; j star 1; } else { // 无星号可用直接失败 return false; } } // s已经走完但p可能还有剩余剩余部分必须全是星号 while (j p.size() p[j] *) { j; } return j p.size(); } };这段代码看起来简单但写对并不容易。最容易忘的其实是最后的那个while循环s全匹配完但p还挂着几个星号这种情况是要算匹配成功的。有一次我在本地用例里跑了半天没发现问题提交后挂在一个huge的用例上最后debug发现就是漏了这行。还有一点star初始化成-1有个作用判断系统中是否存在可回溯的星号。如果star等于-1说明前面没有任何星号那当前字符失配就是真失配直接return false。这个哨兵值的运用是很多老手惯用的技巧能有效避免单独用一个布尔变量判断。3.3 复杂度对比与实测数据我这里把两种解法在几组不同长度的输入上跑了一下对比供你直观感受差距。测试环境就是普通的本地编译器不涉及任何外在因素纯看算法本身的耗时。输入规模DP耗时毫秒双指针耗时毫秒s长度100p长度100约0.2约0.1s长度1000p长度1000约8约3s长度10000p长度10000约380约160极端回溯型输入约420约300从数据能看出来双指针在绝大多数场景下确实比DP快一截主要原因是它根本没有把整张表全部遍历完很多分支走一步就直接回溯跳过了。不过DP的耗时非常稳定几乎不会出现极端情况的大幅波动而双指针在“大量星号互相纠缠”的输入下可能退化到接近O(m*n)。选择哪种取决于你更看重稳定性还是极致的空间利用。4. 实操中常见的坑与排查技巧4.1 空串与星号组合的边界用例我见过太多人在这道题上栽在“空串”手里包括我自己第一次提交时也被坑过。具体来说有这么几组用例是必须提前测的s p 应该返回trues p *应该返回trues p ****应该返回trues p a应该返回falses ap 应该返回false这些用例的共性都在于它们能逼你把base case想清楚。特别是s为空但p包含非星号字符的情况很多人的DP初始化会把dp[0][j]一路设置成true导致错误地认为空串能匹配任意模式。我自己的习惯是动笔写代码前先把这些用例在草稿纸上跑一遍确认dp[0][j]的递推逻辑只允许星号把空串匹配掉再开始动手。4.2 双指针方案里的存档回退双指针方案里有一个隐蔽的坑就是星号回溯之后之前普通匹配的进度可能“错位”。我举个例子s aaabp a*b。第一次走到星号时s_tmp记在第二个a的位置然后尝试让星号匹配空串结果后面b和s的b对不上于是回退s_tmp星号吞掉第二个ai重新指向第三个a再往后匹配。这个回退过程要重复两次才能最终让星号吞掉两个a。如果你在回退时把s_tmp的位置更新错了就会出现死循环或者漏匹配。我调试时常做的一步是在star分支和回退分支各打印一行i、j、s_tmp的值肉眼观察它们是不是按预期推进。这个方法虽然原始但比对着代码空想高效得多。4.3 用测试用例驱动调试说到调试我强烈建议你养成一个习惯先准备一组覆盖各种情况的测试用例再动手写代码。这里的用例不光是上面那些边界情况还要覆盖普通字符完全吻合、?连续出现、星号在开头/中间/结尾、多个星号连续出现、大小写混合等场景。我一般是这么组织测试用例的测试目的sp期望结果完全相等abcabctrue?替换单字符abca?ctrue星号匹配空串abca*ctrue星号匹配多字符abcdefa*ftrue星号在开头abc*bctrue星号在结尾abcabc*true连续星号abcabctrue不匹配的场景abca?dfalse大小写敏感aAfalse这些用例覆盖了绝大多数逻辑分支跑通了它们代码基本上就不会有大问题。LeetCode上提交失败的话错误用例本身也别放过把输入拆到最小维度去复现往往两分钟就能定位到问题。5. 30天刻意练习的方法论沉淀5.1 刻意练习到底在练什么整个系列当初起名“刻意练习”其实是借用了某个经典的学习理论框架。简单说它强调的不是盲目刷题的数量而是在“舒适区边缘”反复挑战自己刚好够不着的东西拿到反馈后立刻修正再上升一个难度层级。落实到LeetCode实战里我的操作方式就三条第一每道题先独立思考30分钟想不出来再看题解绝不一上来就翻答案第二AC之后必须看官方题解或讨论区的高赞解法学习有没有比自己更妙的思路第三隔三天把同类型题目拿出来对比着再刷一遍检验自己是不是真记住了。这套方法坚持30天下来我最大的体会是慢慢会形成一种“条件反射”看到字符串匹配想DP表看到最值问题想二分或贪心看到子串问题想双指针滑动窗口。25天之后很多东西已经不需要刻意去想经验就长在脑子里了。5.2 这类题目沉淀下来的通用套路通配符匹配作为完结篇特别合适因为它几乎把前面所有题的套路都串起来了。从这道题往后看你会发现字符串匹配类问题基本逃不出这几个框架单字符串的子串匹配优先考虑滑动窗口双字符串的匹配判断画一个二维DP表状态就是“两个串各自的前缀”如果状态转移里出现“或”逻辑多半有一个分支是“当前字符匹配”另一分支是“跳过当前字符”如果某个字符有“任意匹配任意长度”的能力星号、通配符模板永远是“匹配空串”加“匹配当前字符”两条路遇到同类的题比如正则表达式匹配、编辑距离、两个字符串的删除操作都可以拿来在这套框架里套一遍。你会发现它们的DP表格长得非常像区别只在状态转移方程的几个分支上。这就是做算法题最值钱的感觉你看得到题目之间的联系而不是每一题都孤零零地从零开始。5.3 最后的一点个人忠告30天完结不是终点而是个起点。我自己踩过最大的坑是前十天特别容易陷入“看题解以为自己会了第二天又忘了”的循环。后来我强迫自己每道题都在文章里把思路写出来不是抄代码是讲人话。发现能把思路讲明白的题基本就是真会了讲不明白的题隔天必忘。这套“讲人话”的输出方法是我整个系列做得最值的一件事。如果你也是刷题刷到瓶颈不妨试试像我这样别再刷新题了把做过的30道题翻出来挑10道最经典的尝试不看代码实现一遍再在纸上画一遍状态转移表。能画出来说明你的算法骨架已经立住了。画不出来也没关系回到那篇文章里重新读一遍这个“回炉”的过程本身就是刻意练习的一部分。希望这篇完结篇不只让你学会通配符匹配这一道题而是能把这30天的练习心得延续到你接下来的每一次刷题里。