企业官网建设流程全解析

1. 从字符串匹配到动态规划：为什么这道题值得认真做

力扣第 10 题 Regular Expression Matching，也就是常说的正则表达式匹配，标题里带个"字符串编辑"并不算夸张——虽然它不是传统意义上的编辑距离问题，但整个状态推导的思路，和编辑距离的 DP 表设计几乎是一个模子刻出来的。这道题在力扣里属于"热题 100"的高频题，也是面试中动态规划方向的经典代表。很多人第一次看到题目就懵了：正则匹配不是语言内置功能吗？手写一个支持.和*的匹配器到底想考什么？

其实这道题剥掉外壳，考的核心只有两件事：状态怎么定义，以及状态怎么转移。.匹配任意单个字符是简单的，真正的难点集中在*上——它表示前面的字符可以重复 0 次或多次。也就是说，a*可以匹配空字符串、a、aa、aaa，甚至更多。这种"0 次"的存在，让整个匹配问题从简单的逐字符比较，升级成了一个需要回溯或动态规划才能解决的问题。

我用实际体验给个结论：直接写递归回溯，代码短，但遇到长字符串容易超时；用动态规划，空间换时间，写清楚状态定义后反而是最稳的思路。本篇文章就把这条路径完整走一遍：从递归的直觉想法出发，再推导到 DP 状态转移表，最后给出一份可以直接提交的代码，顺带把边界条件和性能陷阱也一并拆开讲。

适合阅读这篇文章的读者有两类：一是刷力扣但卡在这道题上的新手，二是工作多年想快速复习动态规划思路的开发者。无论你基础如何，只要耐下心把状态转移图在纸上画一遍，这道题就真正属于你了。

2. 暴力递归：先用直觉理解通配逻辑，再考虑优化

拿到这道题，我建议你别急着写 DP，而是先尝试用递归去表达匹配逻辑。递归的思维负担最小，也最容易验证你理解的匹配规则是否正确。通过递归跑通几个用例后，再看它哪里慢、慢到什么程度，你会对后续 DP 优化的价值体会更深。

2.1 匹配规则拆解：.、*和普通字符各管一摊

先明确一下要实现的匹配规则，很多人失分就是失在没彻底理解*的语义上：

• 普通字符a：只能匹配字符串中对应的字符a。
• .：可以匹配任意单个字符，但注意是"任意单个"，不能多匹配也不能少匹配。
• *：不能单独出现，必须跟在某个字符后面，表示前面的字符可以重复 0 次或多次。这里最重要的是"0 次"，意味着模式中的a*可以对应字符串中不存在任何a。

还有一个关键点：*前面是.时，.*可以匹配任意长度的任意字符序列，这是很多复杂用例的核心来源。

2.2 递归分支怎么走：遇到*就是两种选择的岔路口

我先把递归函数定义成match(i, j)：表示从文本串s的第i个位置开始、模式串p的第j个位置开始，两段是否匹配。这个定义清晰直观，也是后面 DP 表状态的同款定义。

递归的核心逻辑可以分成三步：

1. 如果j已经走到模式串末尾，那必须i也走到文本串末尾才返回True。
2. 当前两个字符是否匹配，用currentMatch记录：当i < len(s)且p[j]等于s[i]或p[j]等于.时，认为当前字符位匹配。
3. 关键判断：如果j + 1 < len(p)且p[j+1]是*，那么有两种选择：
   • 选择一：让p[j]匹配 0 次，直接跳过模式和星号，即match(i, j + 2)。
   • 选择二：如果当前这一位匹配成功，让p[j]匹配一次后，继续用同样的模式去匹配s[i+1]，即currentMatch and match(i + 1, j)。

这种"0 次还是继续匹配"的二元选择，正是*的灵魂所在。

以下是我在最开始验证逻辑时写的 Python 递归版本，逻辑直白到可以直接对照上面文字看：

def isMatch(s: str, p: str) -> bool: def match(i: int, j: int) -> bool: if j == len(p): return i == len(s) current_match = i < len(s) and (p[j] == s[i] or p[j] == '.') if j + 1 < len(p) and p[j + 1] == '*': # 跳过 x* 匹配 0 次，或者当前位匹配后继续消耗 s return match(i, j + 2) or (current_match and match(i + 1, j)) # 没有星号，老老实实匹配一位 return current_match and match(i + 1, j + 1) return match(0, 0)

这段代码跑中小规模的用例没有任何问题，逻辑也很容易读。但你连续跑几个复杂用例就会发现，性能非常不稳定。原因在于match(i, j)可能被重复计算：比如s = "aaaaaaaaa"、p = "a*a*a*a*a*a*a*a*b"这种输入，递归树会爆炸式增长，重复计算同一状态的情况非常严重，超时几乎是板上钉钉的事。

我试过在递归里加个字典做记忆化，也就是memo = {}来缓存每个(i, j)的结果。加完之后性能有了质的提升，这其实已经是在向 DP 过渡了——因为缓存的状态和 DP 表的单元格一一对应。这个现象建议你自己跑一下感受感受，理解了递归慢在哪，再去看 DP 表的迭代填充，思路就通了。

3. 动态规划状态定义与转移方程：一张二维表把所有情况装下

递归加记忆化虽然可行，但面试官更希望看到你能直接写出 DP 的迭代版本。核心原因有两个：一是迭代没有递归调用栈溢出的风险，二是 DP 表的填充过程更容易做复杂度分析，也更容易向其他字符串问题迁移。

3.1 为什么用二维 DP 而不是一维：两个字符串的匹配天然需要二维坐标

匹配的本质是比较两个序列的对应关系，所以状态不仅依赖文本串的当前位置，还依赖模式串的当前位置。用dp[i][j]表示s的前i个字符和p的前j个字符是否匹配，这里的i和j是长度而不是下标，这一点极重要。

为什么用长度而不是下标？因为我们需要自然表达空串和空模式：dp[0][0]是 True，即空文本匹配空模式。如果从 0 下标开始，空串就得用-1表示，处理起来非常痛苦。用长度定义后，dp[i][j]天然覆盖了s[:i]和p[:j]的完整前缀，边界条件也更清晰。

3.2 转移方程的推导过程：从递归分支反推表格填法

递归的思路是从头往后看，而 DP 是从短的子串开始，逐步构造长串的匹配结果。我把转移逻辑拆解成四种情况，这样对照代码时不会晕：

第 3 种情况是全题最容易漏的。a*匹配空，意味着模式里多出两个字符，但文本没有增加任何内容，所以dp[i][j-2]直接传递过来。第 4 种情况需要仔细品味：dp[i-1][j]的含义是，在s已经少一个字符时，当前模式和它匹配成功，那么现在s多了一个字符，只要这个字符满足了*前驱的要求，也能匹配成功。

用一个具体例子走一遍数据流。设s = "aa"、p = "a*"：

• dp[0][0] = True，空匹配空。
• dp[0][1]：p[0] = 'a'是普通字符，但s为空，所以 False。
• dp[0][2]：p[1] = '*'，走第 3 种情况，dp[0][2] = dp[0][0] = True。这里就体现了a*匹配空串的能力。
• dp[1][2]：p[1]是星号，当前字符s[0] = 'a'匹配p[0] = 'a'，于是走第 4 种情况，dp[1][2] = dp[0][2] = True。
• dp[2][2]：同理，dp[2][2] = dp[1][2] = True。

这个链条的传递逻辑很优雅：dp[0][2]是真，就像多米诺骨牌一样逐级向右下方推。你多填几行几列，会明显感受到这种递推的美感。

3.3 初始化边界：dp[0][j]这一行最容易犯的错

初始化是这道题的高频失分点，主要集中在对dp[0][j]的处理上。空文本的情况下，只有形如a*b*c*的模式才可能匹配成功。因为普通字符和.都至少需要一个文本来匹配，而x*可以整体消失。

所以初始化循环要单独处理j从 2 到len(p)，判断条件是p[j-1] == '*'且dp[0][j-2]为 True。这里要注意括号里的关系：dp[0][j-2]表示往前跳两位的状态，因为x*是两个字符一组的。

写代码时常犯的错是直接初始化为dp[0][j] = True，或者忘记处理dp[0][j-2]的传递，导致a*b*这类模式在空串下全部算错。我建议你在填表前先把这一行的手算结果写出来，比如p = "a*b*c"时，dp[0]行应该长成[True, False, True, False, True, False]，其中每个 True 都源于前一个 True 加一组x*。

4. 完整实现与复杂度分析：从提交的代码到每一步的含义

把状态定义和转移方程想清楚之后，代码本身就不难了。我直接给一份实测过的 Python 解法，并逐步解释每段代码的用意。

4.1 一版可以直接提交的 Python 实现

def isMatch(s: str, p: str) -> bool: m, n = len(s), len(p) # dp[i][j] 表示 s 的前 i 个字符与 p 的前 j 个字符是否匹配 dp = [[False] * (n + 1) for _ in range(m + 1)] dp[0][0] = True # 初始化空文本对应的行：只有 x* 组合能匹配空串 for j in range(2, n + 1): if p[j - 1] == '*': dp[0][j] = dp[0][j - 2] for i in range(1, m + 1): for j in range(1, n + 1): if p[j - 1] == '*': # 星号前驱字符 prev = p[j - 2] # 情况一：匹配 0 次，跳过 x* dp[i][j] = dp[i][j - 2] # 情况二：匹配 1 次及以上，要求当前 s 字符能被 prev 匹配 if prev == '.' or prev == s[i - 1]: dp[i][j] = dp[i][j] or dp[i - 1][j] else: # 普通字符或点号，直接看前一位状态 if p[j - 1] == '.' or p[j - 1] == s[i - 1]: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = False return dp[m][n]

这段代码里有两处细节值得单独说明：

• 在p[j-1] == '*'的分支里，我先无条件地让dp[i][j] = dp[i][j-2]，这一步就是处理"匹配 0 次"的情况。然后再看能否匹配 1 次及以上，用or把两种情况合并。这段逻辑和递归里的match(i, j+2) or (current_match and match(i+1, j))完全对应，只是方向倒过来了。
• 对于普通字符的匹配，我写的是先判断当前字符是否相等，相等才继承左上角的状态。有优化空间的做法是先用dp[i][j] = dp[i-1][j-1]，再用条件判断覆盖，但那样会增加无效赋值，不如直接判断来得清晰。

4.2 时间与空间复杂度：O(mn) 是最优解吗

两层循环遍历了所有(i, j)组合，所以时间复杂度是O(mn)，m是文本串长度，n是模式串长度。空间复杂度同样也是O(mn)，因为完整保存了二维 DP 表。

现在回答一个经常被问到的问题：能不能优化到一维 DP？答案是可以，因为dp[i][j]只依赖dp[i][j-2]（同一行的前两列）和dp[i-1][j]（上一行的同一列）。仔细看依赖关系，其实只需要保留上一行的完整结果就能滚动更新。但我要提醒一点：dp[i][j-2]是同一行的数据，这意味着在遍历 j 时，当前行的前两列必须已经更新过。所以一维优化需要注意内层循环的方向和临时变量的保存，稍不留神就会用错数据。面试时如果想表现更深的功底，可以先交出二维版本，再主动提一维优化的思路。

用一维数组替换的参考代码如下，逻辑与二维版完全对应：

def isMatch_1d(s: str, p: str) -> bool: m, n = len(s), len(p) prev = [False] * (n + 1) # 初始化第 0 行 prev[0] = True for j in range(2, n + 1): if p[j - 1] == '*': prev[j] = prev[j - 2] for i in range(1, m + 1): curr = [False] * (n + 1) curr[0] = False # 非空文本永远匹配不了空模式 for j in range(1, n + 1): if p[j - 1] == '*': curr[j] = curr[j - 2] if p[j - 2] == '.' or p[j - 2] == s[i - 1]: curr[j] = curr[j] or prev[j] else: if p[j - 1] == '.' or p[j - 1] == s[i - 1]: curr[j] = prev[j - 1] prev = curr return prev[n]

空间复杂度从O(mn)降到了O(n)，这对于m和n都很大时非常关键。不过说句实在话，刷题阶段如果你能完整写出二维版本并讲清楚转移，已经能过绝大多数面试了；一维优化更像是一个加分项，用来展示你对状态依赖关系的理解粒度。

4.3 两个容易出错的分支，单独拎出来说

在我实际调试中，有两个特例经常让结果瞬间变错，这里单独拎出来强调。

第一个是模式串以*开头，比如p = "*abc"。按照规则，*必须跟在某个字符后面，所以这种输入属于非法模式。力扣测试用例里一般不会出现，但如果你自己写测试，要注意先做合法性校验或者依赖题目的约束。

第二个是.*的情况。这是最能体现*与.联合威力的组合：.*能匹配任意长度的任意字符串。在 DP 转移里，它对应的是"当前字符是*，前驱是.，于是只要prev[j]为 True，后续所有行都能从这里一路传下去"。我曾用s = "abcdef"、p = ".*"手动填表，发现dp[0][2]是 True 后，整列的状态都会沿着dp[i-1][j]一路传递到dp[6][2]，这就是为什么.*能吞掉一切字符——它在表格里形成了一条真正的"直通车"。

5. 从这道题延伸出的通用技巧：字符串编辑问题到底在考什么

刷完这题别急着走。Regular Expression Matching 的价值不只是背会一套转移方程，它背后代表的是字符串编辑这一类问题的通用方法论。把这道题的收获抽象出来，你对这类题的抗性会提升一个档次。

5.1 字符串编辑类题目的共性套路

先看几道和本题思路相近的经典题：编辑距离（Edit Distance）、不同的子序列（Distinct Subsequences）、通配符匹配（Wildcard Matching）。它们的共同点是：两个字符串之间的某种匹配关系或转换代价，并且这种关系可以用子问题来递推。

处理这类题的通用套路，我自己总结成四步，按顺序走基本不会乱：

1. 定义状态，优先使用"长度"作为维度。也就是dp[i][j]表示第一个串的前i个元素与第二个串的前j个元素之间的关系。
2. 确定终止状态，也就是边界条件，通常是dp[0][0]、dp[0][j]、dp[i][0]这三个位置。很多人一上来急着写转移方程，边界却没想清楚，结果越写越乱。
3. 写出转移方程时，先想最后一对字符会如何处理。是匹配？替换？删除？还是像*一样可以跳过？这一步决定了方程的内核。
4. 最后再考虑空间优化。不要一上来就写滚动数组，二维表能帮你理清思路，想清楚了再压缩。

拿编辑距离举例，如果没刷过可以现在就对比感受一下：dp[i][j]表示word1[:i]转成word2[:j]的最小编辑次数，转移方程考虑增、删、改三个方向。和本题相比，编辑距离是多个方向的代价比较，而本题是匹配与否的布尔传递。底层框架是一致的，只是每个题目的操作集合不同。

5.2 如何快速判断一道题该用贪心、递归还是 DP

这是个更宏观的问题。我的经验是：如果一个题目里存在"选择"，而且选择之后产生的影响会波及后续多个字符，那就基本告别贪心了。因为贪心只能解决局部最优即是全局最优的场景，而匹配类问题里，看似合理的一次选择很可能把后面的路堵死。

那怎么区分递归和 DP？如果你发现递归的分支会反复访问相同的(i, j)状态，就像地图上多条道路汇聚到同一个交叉口，那就应该上记忆化或 DP。我习惯用的快速验证方法是：随便构造一组输入，手动画一下递归树，只要出现两个相同的节点，就说明有重叠子问题。这道题里match(1, 3)可能在递归树里出现七八次，重叠概率非常高，所以 DP 势在必行。

5.3 刷题时如何高效整理这类"同构题"笔记

我自己刷题有个习惯，会把同构题放在一起做对比分析，而不是只追求 AC 数量。比如把第 10 题、第 44 题通配符匹配、第 72 题编辑距离放在同一个表格里对比，效果远好于一道题刷十遍。

下面这张对照表是我做笔记时用的格式，也分享给你：

每次整理笔记时，我还会顺手写清"踩过的坑"一栏。比如本题的坑是dp[0][j]初始化，通配符匹配的坑是*独立匹配任意串不需要前驱，编辑距离的坑是初始化时dp[i][0] = i和dp[0][j] = j必须从 1 开始。这些细节才是真正的护城河，比干巴巴的转移方程值钱得多。

6. 测试驱动的调试思路：用边界用例把 DP 表逼到极限

写完了代码不测试等于白写。这道题最需要小心的不是逻辑本身，而是各种边界组合。我建议你建立一个自己的边界用例清单，AC 之前先跑一遍，AC 之后也保留着，避免后续改代码时回归出问题。

6.1 必须覆盖的用例清单

以下是我实测时用过的清单，按难度从基础到刁钻排列：

这几个用例涵盖了初始化、0 次匹配、多次匹配、点星组合、长文本复杂模式等几乎所有关键分支。我在调试"mississippi"时，曾经因为dp[i][j]里or的顺序写错，导致星号分支只执行了 0 次匹配而丢掉了多次匹配的结果，最后就是靠这个用例揪出来的。

6.2 打印 DP 表：排错效率最高的手段

遇到结果不符合预期时，不要盯着代码干瞪眼，直接把整个 DP 表打印出来，一眼就能看出哪一步断掉了。我在本地调试时常在返回前加一段辅助代码：

for row in dp: print(row)

输出长这样（以s = "aa"、p = "a*"为例）：

[True, False, True] [False, False, True] [False, False, True]

这个表格非常直观：第一行中dp[0][2]为 True 表示a*匹配空串；第二行dp[1][2]为 True 表示a*匹配"a"；第三行dp[2][2]为 True 表示匹配"aa"。如果某一步该出现的 True 没出现，看它依赖的上游状态，很快就能定位到是初始化问题还是转移方程问题。

我曾经在一次面试准备中打印过十来个用例的 DP 表，一边打印一边在纸上对应转移方程，那次之后我对这道题的掌握程度直接从"能背代码"变成了"能随手推导"。强烈建议你也试试这个方法。

6.3 关于 leetcode 输入边界：不要认为模式永远合法

力扣题目通常会限制输入合法性，但很多扩展场景里模式串可能包含非法的连续星号或首字符星号。如果你要在生产代码中实现类似功能，一定要在进入 DP 之前做模式合法性校验。一个简单的校验思路是：遍历模式串，遇到*时检查其前一个字符是否存在，不存在则返回非法。这道题本身不需要，但了解这一点对迁移到真实场景很重要。

7. 与编辑距离等同类问题的对比思考：一通百通的字符串动态规划

既然热搜词把这道题和"字符串编辑"联系在一起，我就顺着这个角度再展开一层。正则表达式匹配虽然不是编辑距离，但把它和编辑距离放在一起看，你会对字符串类动态规划有更整体的认识。

7.1 正则匹配 vs 编辑距离 vs 通配符匹配的差异

三道题都叫"双串 DP"，但差异点非常值得品味：

• 编辑距离：状态值是一个距离数值，转移时要做三个方向的最小值比较。它关心的是最少操作次数，而非是否可达。
• 通配符匹配：*独立存在，能匹配任意字符串序列，不需要看前驱字符。它的转移方程是dp[i][j] = dp[i-1][j] or dp[i][j-1]，简洁到只需处理两个分支。
• 正则匹配：*依赖前驱字符，所以多了一个"检查当前文本字符是否能被前驱匹配"的条件层。星号本身不能独立行动，必须先看它前面站的是谁。

这个差异在代码量上就体现出来了：通配符的星号分支只需要两行，而正则匹配的星号分支往往要四五行。本质上，正则比通配多了一层"绑定关系"，处理起来自然更繁琐。

7.2 从一道题到一类题：把 DP 表当作转移图来理解

很多人学会一道题后，换一道类似的题就懵了。我自己的经验是，别把 DP 表只看成一个二维数组，而要把每个单元格看作一个"状态节点"，把转移关系看作节点之间的有向边。

拿本题来说，dp[i][j]= True 意味着存在一条从dp[0][0]到dp[i][j]的路径。a*之所以能匹配任意长度的a，本质就是表格上存在一条沿着对角线方向不断延伸的绿光大道。每当你遇到新的双串 DP 题，先问自己：状态图里的"边"是什么？路径的存在条件是什么？这张图画清楚了，转移方程基本上也就写出来了。

我有一位同事刷题时习惯用纸笔把所有 DP 格子涂成黑白两色，黑色表示 True。他说看到黑色区域在不同形状下的分布，就能发现题目之间的深层次差异。这个方法听起来有点玄，但你试一次就会体会到它的好处——它逼着你从"记忆转移方程"升级为"理解状态流动"。

8. 实际刷题中的节奏建议与高频失误汇总

最后总结下我们在真实刷题过程中可能会遇到的坑，以及怎么管理刷这道题的节奏。这些内容不算什么高深理论，但都是我踩过的真实经历，分享出来希望你能少走弯路。

8.1 高频失误 Top 5

第五个坑是我特别要强调的：Python 里数组索引为负时不会报错，而是从尾部取值，这比 Java 或 C++ 的越界崩溃更隐蔽，因为你根本看不到异常提示。我在一次刷题时用一维数组实现，某个状态本应访问curr[j-2]，但因为 j 从 1 开始，j-2 = -1，结果取到了末尾元素，导致结果完全不可预测。调试了很久才发现是负数索引惹的祸。这类问题在力扣的测试用例下尤其隐蔽，因为有的用例恰好能过，有的就会挂。

8.2 建议的刷题节奏：从理解到 AC 再到变体

我给这道题定的刷题节奏是这样的，也推荐你按这个顺序走：

1. 第一天：读题，拿纸笔自己画状态转移图，尝试写递归版本，跑通基础用例。
2. 第二天：不参考任何题解，把递归改成记忆化，感受性能变化；然后再推导 DP 迭代版。
3. 第三天：实现一维滚动数组版，并主动跑一遍边界用例清单。
4. 第四天：做同构题对比，把通配符匹配、编辑距离一起刷掉，写对比笔记。

这个节奏看着慢，但效果很扎实。我见过太多人一天连刷十几道题，AC 完就忘，下次见面像是从没见过。动笔推导和手画表格的时间，其实是在帮大脑建立真正的长期记忆。

另外给你一个实用的建议：AC 之后别急着刷下一题，花十分钟写一段"为什么这样设计"的注释放进代码里。比如在星号分支旁边写"这里先赋值 0 次匹配，再用 or 合并多次匹配，与递归的 match(i,j+2) or currentMatch and match(i+1,j) 对应"。下次复习时，你看到注释就能在 30 秒内恢复完整记忆，比重新看一遍题解快得多。

9. 一个提高可读性的改进版本与个人风格

读到这里，再回到代码本身。很多人刷题追求代码最简，但我倒是认为，代码的可读性往往比行数多少更重要。在面试场景里，清晰的变量命名和结构化的分支，能帮你和面试官建立更好的沟通。下面这个版本是我根据个人习惯整理的，逻辑与标准 DP 一致，但命名更友好：

def isMatch(s: str, p: str) -> bool: text_len, pattern_len = len(s), len(p) dp = [[False] * (pattern_len + 1) for _ in range(text_len + 1)] dp[0][0] = True # 模式串形如 a*b* 时，可以匹配空文本 for j in range(2, pattern_len + 1): if p[j - 1] == '*': dp[0][j] = dp[0][j - 2] for i in range(1, text_len + 1): for j in range(1, pattern_len + 1): if p[j - 1] == '*': zero_match = dp[i][j - 2] current_char_match = p[j - 2] == '.' or p[j - 2] == s[i - 1] one_or_more_match = current_char_match and dp[i - 1][j] dp[i][j] = zero_match or one_or_more_match else: if p[j - 1] == '.' or p[j - 1] == s[i - 1]: dp[i][j] = dp[i - 1][j - 1] return dp[text_len][pattern_len]

这个版本把星号分支拆成了zero_match和one_or_more_match两个变量，再合并。阅读时的语义非常清晰：一个处理"用 0 次"，一个处理"用 1 次及以上"。如果你觉得zero_match这个名字太长，也可以简写为skip_star，但核心是让人一眼看明白变量的作用。

有一点我特别想说：不要为了和题解写得一模一样而放弃自己的风格。只要能正确实现匹配逻辑，变量名长短完全看个人习惯。面试官更看重你能不能用语言把每一行代码的动机讲清楚，而不是代码是否以最短形式呈现。

我在实际刷题过程中发现，把这个版本和记忆化递归版本放在一起对比，对初学者尤其友好。因为两个版本的分支结构可以一一对应，读代码时就像在对照两份翻译：一份是自上而下的自然推导，一份是自下而上的表格填充。看多了这种对照，你对递归与动态规划之间的转换就会越来越顺手。