企业官网建设流程全解析

做算法题这些年，如果让我评一道"看起来不难、写起来想哭"的经典题目，正则表达式匹配绝对榜上有名。它在LeetCode上是第10题，标着Hard难度，但考察的核心算法思想并不冷门——递归、动态规划、状态转移，每一个都是面试高频考点。真正让新手翻车的，往往是题目里那个星号的语义：它和我们平时写正则时理解的"通配任意字符"完全是两码事。这篇文章就用这道题为例，把从暴力递归到动态规划的完整推导过程、代码实现和踩坑点一次讲清楚。无论你是在校刷题、准备面试，还是工作中需要写解析器，都能照着推演一遍。

1. 题目到底在问什么——先把规则吃透

1.1 题干回顾与两个特殊字符的真实含义

题目要求实现一个支持'.'和'*'的正则表达式匹配函数，判断字符串s是否能被模式串p完全匹配。注意是"完全匹配"，不是"包含匹配"，这就意味着从头到尾都要对上。

两个特殊字符的含义要背下来：

• '.'匹配任意单个字符，比如s='a'、p='.'返回 true。
• '*'匹配零个或多个前面的那一个元素，比如s='aa'、p='a*'返回 true，因为'a'重复了两次；s='b'、p='a*b'也返回 true，因为'a*'可以表示零个'a'。

这是最容易误解的地方。平时我们用正则表达式，很多人以为*是"匹配任意内容"的通配符，但在这道题里不是，*只是"修饰前一个字符"的符号。一个x*整体才表示"零个或多个 x"，*不能单独出现。

看几个典型例子：

• s = "aa"，p = "a"→ false，因为'a'只能匹配一个'a'。
• s = "aa"，p = "a*"→ true，'a'重复两次。
• s = "ab"，p = ".*"→ true，'.'匹配'a'，'.*'整体表示"任意字符重复零次或多次"，匹配'b'绰绰有余。
• s = "aab"，p = "c*a*b"→ true，'c*'表示零个'c'，'a*'表示两个'a'，再加上'b'。
• s = "mississippi"，p = "mis*is*p*."→ false，最后一段'p*.'无法覆盖结尾的'i'。

如果你第一次做就把.*理解成"任意字符任意次数"，那后面的状态转移一定会乱。先把这层纸捅破，后面都是常规操作。

1.2 容易理解错的几个点

结合我平时带人刷题的经验，下面这几个点几乎人人都会踩：

第一，'*'不能单独出现，它必须跟在某个字符后面。虽然题目保证了输入合法，但初写代码时很容易在判断条件里漏掉p[j-2]这个"前一个字符"。

第二，必须匹配整个字符串。有些人写递归时习惯性地一旦发现某个字符对不上就返回 false，完全没考虑'*'可以把前面的字符清空。比如p = "a*b"和s = "b"，显然应该匹配，但如果你逐字符扫，第一步就发现s[0]='b'对不上p[0]='a'，直接返回 false 就错了。

第三，'*'的匹配次数不是固定的，题目不会按"贪婪模式"或"非贪婪模式"来约定。它只是说"零个或多个"，所以我们需要自己把各种可能性都试一遍，或者用动态规划记录所有前缀状态的匹配结果。这也是为什么这道题天然适合递归回溯和 DP，而不能靠简单的线性扫描。

第四，这道题和 LeetCode 44 通配符匹配很像，但别搞混。44 题里'*'是可以匹配任意字符串的通配符，和本题的"修饰前一个字符"是两套规则。面试时如果和这道题对比着问，一定要先确认规则再写代码。

2. 解法拆解：从暴力递归到动态规划的思路演进

2.1 递归回溯：用枚举所有可能性解决匹配问题

最容易想到的解法是递归回溯，思路非常直白：从s和p的第一个字符开始逐个匹配，遇到'*'时尝试"匹配零次"或者"匹配一次继续"，把剩下的字符串丢给递归函数去处理。

具体来说，假设有两个指针i和j分别指向s和p的当前位置，匹配逻辑可以这么梳理：

• 如果j走到了p的末尾，那么只有当i也走到s的末尾时才算匹配成功。
• 如果p[j+1]不是'*'，那么当前字符必须能匹配上，再继续匹配s[i+1:]和p[j+1:]。
• 如果p[j+1]是'*'，有两种选择：
  • 匹配零次：直接跳过p中的当前字符和*，去匹配s[i:]和p[j+2:]；
  • 匹配一次或多次：如果当前字符能匹配上，保留p中的x*，去匹配s[i+1:]和p[j:]。

写成 Python 就是下面这样：

def isMatch(s: str, p: str) -> bool: if not p: return not s first_match = bool(s) and (p[0] == s[0] or p[0] == '.') if len(p) >= 2 and p[1] == '*': # 匹配零次 或 匹配当前字符一次（继续保留 x*） return (first_match and isMatch(s[1:], p)) or isMatch(s, p[2:]) else: return first_match and isMatch(s[1:], p[1:])

这个写法很简洁，但要注意，它最坏情况下的时间复杂度是指数级的。比如模式串是"a*a*a*a*"这种连续重复的结构，每次遇到'*'都要分叉成两个分支，整体就变成了 2 的 n 次方级别的搜索。

我当时第一次交这个递归版本，在小用例上能过，但 LeetCode 上某些测试用例直接超时。这让我意识到，必须把已经算过的子问题结果缓存下来，或者干脆改成自底向上的动态规划。

2.2 动态规划：自底向上把子问题结果存起来

动态规划的思路是消除重叠子问题。回到刚才的递归过程，你会发现isMatch(s[i:], p[j:])这个子问题被反复计算了很多次。比如'a*'匹配'aaa'的过程，每次"匹配一次"分支都会重新计算同一对(i, j)状态。

所以我们可以定义一个二维布尔数组dp，其中dp[i][j]表示s的前i个字符和p的前j个字符能否匹配。

这里要注意下标偏移：dp[i][j]对应的是s[0:i]和p[0:j]，也就是s的前 i 个字符。这样定义的好处是方便处理空串的情况，dp[0][0]表示两个空串匹配，结果自然是 true。

状态转移分两种情况：

第一种，p[j-1]是普通字符或者'.'。只要s[i-1]能匹配上p[j-1]，那么dp[i][j]就等于dp[i-1][j-1]。因为当前这两个字符消掉之后，就看前面的前缀是否匹配。

第二种，p[j-1]是'*'。此时要看p[j-2]是什么：

• 如果p[j-2]和s[i-1]不能匹配，说明x*只能表示零个x，那么dp[i][j] = dp[i][j-2]，相当于把x*直接扔掉。
• 如果p[j-2]能匹配s[i-1]，那么x*可以选择匹配一个x，此时dp[i][j] = dp[i-1][j]；也可以选择匹配零个，此时dp[i][j] = dp[i][j-2]。两种情况只要一个成立就行，所以取或运算。

这个dp[i-1][j]是这类题最容易写错的地方，很多人会写成dp[i-1][j-1]，少算了一种"x*继续匹配多个 x"的情况。记住一个口诀：遇到*，考虑"匹配零个"和"匹配一个继续循环"这两条路，前者去掉x*，后者只消费s中的当前字符但保留x*。

2.3 记忆化搜索：递归 + 缓存，两种思路的统一视角

在递归框架上直接加一个缓存，就能把指数级复杂度降下来，这种方案叫记忆化搜索。它和 DP 在本质上是等价的，只是计算方向不同：一个是"从前往后递归、边算边缓存"，另一个是"从后往前填表"。

from functools import lru_cache def isMatch(s: str, p: str) -> bool: @lru_cache(None) def dfs(i: int, j: int) -> bool: if j == len(p): return i == len(s) first_match = i < len(s) and (p[j] == s[i] or p[j] == '.') if j + 1 < len(p) and p[j + 1] == '*': return (first_match and dfs(i + 1, j)) or dfs(i, j + 2) else: return first_match and dfs(i + 1, j + 1) return dfs(0, 0)

用记忆化搜索的好处是思路更贴近递归直觉，代码也短。我个人的习惯是：面试时如果时间紧张，先写记忆化搜索保证正确性，再和面试官聊怎么优化成二维 DP 表格。

三种方法的特点对比如下：

这里 m 和 n 分别是s和p的长度。空间上其实还可以优化成一维数组，但面试时能用二维 AC 已经是 90 分了，等代码跑通后再提优化空间，效果会更好。

3. 动态规划完整实现与关键细节

3.1 代码实现与逐行注解

直接给一个能 AC 的 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 # 初始化空串 s 匹配模式串 p 的情况 # 只有形如 a*b*c* 的模式才能匹配空串，遇到 '*' 就把前一个字符连用零次 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] == '*': # '*' 表示前一个字符 p[j-2] 出现零次或多次 # 情况1：出现零次，直接丢弃 p[j-2] + '*' # 情况2：出现一次以上，前提是 p[j-2] 能匹配当前字符 s[i-1] if p[j - 2] == '.' or p[j - 2] == s[i - 1]: dp[i][j] = dp[i][j - 2] or dp[i - 1][j] else: dp[i][j] = dp[i][j - 2] 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]

如果你用的是 C++，版本也一并放上来，方便对比记忆：

class Solution { public: bool isMatch(string s, string p) { int m = s.size(), n = p.size(); vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false)); dp[0][0] = true; for (int j = 2; j <= n; j++) { if (p[j - 1] == '*') { dp[0][j] = dp[0][j - 2]; } } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p[j - 1] == '*') { if (p[j - 2] == '.' || p[j - 2] == s[i - 1]) { dp[i][j] = dp[i][j - 2] || dp[i - 1][j]; } else { dp[i][j] = dp[i][j - 2]; } } else { if (p[j - 1] == '.' || p[j - 1] == s[i - 1]) { dp[i][j] = dp[i - 1][j - 1]; } } } } return dp[m][n]; } };

3.2 状态转移表怎么填：手动推演一遍

光看代码不够，我建议你拿出一张草稿纸，跟我手动推演一个例子：s = "aab"，p = "c*a*b"。下面这张表就是 dp 数组的内容，行表示s的前缀长度，列表示p的前缀长度，从左下角往右上角看。

推导过程是这样的：

• dp[0][0] = true，两个空串匹配。
• dp[0][2]：模式串是c*，让c出现零次，匹配空串，所以是 true。
• dp[0][4]：模式串是c*a*，c*消掉，a*也消掉，所以是 true。
• dp[1][1]：s='a'对p='c'，不匹配，false。
• dp[1][3]：s='a'对p='c*a'，前面的c*消掉，a匹配a，所以 true。
• dp[1][4]：s='a'对p='c*a*'，这一步是关键，dp[1][4] = dp[1][2] || dp[0][4]。dp[1][2]是 false（a对c*匹配不了），但dp[0][4]是 true，表示a*匹配空，然后a被a*吃掉一次，所以整体成立。
• dp[2][4]：s='aa'对p='c*a*'，因为a*可以匹配两个a，结果为 true。
• dp[3][5]：最后b匹配b，整体为 true。

如果推到这里，你会发现在'*'的转移中，dp[i-1][j]才是"让x*继续匹配下一个字符"的关键，这也是为什么它要一直保留x*而不是跳过去。手动填这张表还有一个好处：面试时如果被追问，你可以直接在白板上画出这个表，比干讲公式有说服力得多。

3.3 初始化与边界条件的原理

接下来专门说一下初值问题，虽然代码就两行，但原理值得拎出来讲。

dp[0][0] = true比较好理解。难的是空串匹配p不为空的情况。p中只有类似x*y*z*这种模式才能匹配空串，因为每个x*都可以选择"出现零次"。所以初始化循环从j = 2开始，只处理p[j-1] == '*'的列：

if p[j - 1] == '*': dp[0][j] = dp[0][j - 2]

为什么从 2 开始？因为合法的*前面一定有字符，p[0]不可能是*，所以j - 2最小也为 0，不会越界。

另一种可能会漏掉的情况是s不为空但p为空，比如s = "a"、p = ""。这就是dp[1][0]，默认值是 false，符合预期。如果你在两层循环里没有显式处理j=0的列，默认 false 就是正确的。

最后总结一句初始化原则：要把"空串"这个维度单独处理好，否则所有依赖dp[0][j]的转移都会出错。我见过太多人动态转移方程写了一堆，结果因为初始化漏了一行，全部结果翻车，这种低级错误真没必要。

4. 常见错误与调试排查实录

4.1 五个高频踩坑点速查表

写这道题的过程中，我总结了一份高频错误清单，几乎每个都是真实发生的：

我挑两个重点说一下。

第一个是"忘记空串初始化"。很多人的第一版代码是dp[0][0] = True之后直接进两层循环，然后发现s = ""、p = "a*"这个用例过不了。原因很简单：dp[0][2]还是 false。实际上此时a*完全可以把a出现零次，匹配空串是成立的，就是初始化没做。

第二个是*的and/or用错。匹配零次和匹配一次继续是两种互斥的可能，只要有一种成立，dp[i][j]就是 true，所以必须用or。如果你用了and，相当于要求"同时匹配零次和继续匹配"，这本身就矛盾。

4.2 测试用例设计思路与验证方法

很多人写完代码就跑一下示例用例，过了就算完事。但 LeetCode 的用例覆盖面很大，你必须自己设计一套边界用例来验证。

我常用的测试集合是这样的：

("", "") -> true ("", "a*") -> true ("", "a*b*") -> true ("a", "") -> false ("a", "a") -> true ("a", ".") -> true ("a", "ab*") -> true ("aaa", "a*a") -> true ("aaa", "ab*a*c*a") -> true ("aab", "c*a*b") -> true ("mississippi", "mis*is*p*.") -> false ("ab", ".*") -> true ("ab", ".*c") -> false

这些用例覆盖了空串、纯字符、单点、点星组合、多个星号连续等场景。如果这些都能过，这道题基本就稳了。

调试时我还习惯在本地打印 dp 表，尤其当结果和预期不一致时，看表是最快的定位方式。比如想排查s = "aaa"、p = "ab*a*c*a"这个用例，打印出 dp 矩阵后，你会直观地看到哪一行哪一列的状态转移出了问题，而不是靠肉眼盯着代码干瞪眼。

5. 这道题背后的能力考察与刷题建议

5.1 面试官到底在看什么

正则表达式匹配是一道非常典型的"会把简单问题复杂化"的题目，面试官选它，通常不是真想让你实现一个完整的正则引擎，而是考察三件事：

第一，规则理解能力。你能不能把"*"修饰前一个字符这个规则翻译成清晰的子问题？有些人全程在纠结*是不是可以匹配任意字符，这就已经输了。

第二，对重叠子问题和最优子结构的敏感度。暴力递归超时后，能不能立刻想到用 dp 二维数组把中间状态存下来？这几乎是动态规划题目的通用信号：子问题被重复计算，就用缓存或填表。

第三，边界意识。空串、p以*开头、s和p长度差很多，这些边界有没有覆盖？初始化代码能不能写对？很多候选人主循环写得很顺，一到dp[0][j]初始化就卡壳，这一下就能看出平时写代码细不细致。

5.2 如何从这道题迁移到其他字符串 DP 题

这道题的套路一旦吃透，可以直接迁移到一串类似的题目。它们的共同点是：给定两个字符串，求某种匹配或转换关系，状态定义通常都是dp[i][j]表示"一个前缀"与"另一个前缀"的关系。

比如 LeetCode 44 通配符匹配，只是把*的语义换成了"匹配任意字符串"，转移方程马上就变松了：遇到*时，dp[i][j] = dp[i-1][j] || dp[i][j-1]，一个是让*多匹配一个字符，一个是用*匹配空串。理解了本题再看它，就是两分钟的事。

再比如编辑距离，dp[i][j]表示word1[0:i]转换成word2[0:j]的最小操作数，转移时看增、删、改三种操作。虽然目标函数从"布尔值"变成了"最小值"，但状态定义和转移框架和正则匹配是同源的。字符串类的 DP 题，练熟这一题再练三五道同类题，基本就能形成条件反射了。

顺着这个思路，还可以去做一下字符串解码、单词拆分、最长公共子序列这类题目，你会发现它们在二维表格里填数的过程都长得差不多。所谓"经典算法题"的价值就在这里——它值得你反复咀嚼，而不是刷一遍记个答案。

我个人在带团队面试候选人时，其实很少要求候选人死记硬背转移方程，而是会追问一句："如果我把*的规则换一下，你现在的代码哪一行要改？"能把这个问题回答清楚的人，才是真的理解了这个算法。建议你在本地把上面的代码跑一遍，然后亲手把"aab"和"c*a*b"的 dp 表格画出来，再对照着改一两个用例感受一下。这个过程走完，这道题就真正变成你的了。