面试题19：正则表达式匹配

围绕点号和星号的完整串匹配，推导作者三分支递归、备忘录与二维动态规划，并用30组官方测试锁定边界。

学习目标

  • 能用三分支递归或 DP 实现正则表达式（点号和星号）完整匹配
  • 能解释星号将状态拆成"匹配零次"和"匹配多次"的分支
  • 能处理模式与字符串同时到达末尾才成功的终止条件

从“匹配一部分还是匹配全部”开始

先预测：字符串 aaa 与模式 a.a 匹配，但字符串 aaa 与模式 .a 不匹配。点号明明能代表任意字符，第二个模式为什么仍失败？

本题的“正则表达式匹配”不是在字符串里寻找一个可匹配子串，而是要求模式覆盖字符串的全部字符。模式 .a 只能消费两个字符，字符串还剩一个 a，因此失败。只有字符串和模式同时到达末尾才成功，这种契约称为。

题目只支持三种模式元素：普通字符必须与自身相同；消费任意一个字符；修饰它前面的普通字符或点号，使该项可以出现零次或多次。换句话说，点号匹配任意字符，但不能匹配空；星号表示前一字符出现零次或多次，自身不能独立消费字符。

模式只含普通字符、点号和星号a恰好一个aa ✓b ×空 ×.任意一个字符a ✓7 ✓空 ×a*零个或多个a空 ✓a ✓aaa ✓
点号消费一个字符；星号修饰前一项，并允许它出现零次。

例如 ab* 可以匹配 a、ab、abb，却不能匹配 b；因为 b* 可以取零次，而开头的 a 仍必须出现。模式 .* 可以匹配任意长度字符串，包括空串；点号负责每次消费一个字符，星号决定重复次数。

这种受限语法没有括号、选择、字符类和锚点，不能把成熟正则引擎的全部规则搬进来。题目考查的是两个位置如何推进，以及星号怎样制造选择；先把输入语言边界缩清楚，才能让状态定义、证明和测试保持一致。

把一个状态拆成三种选择

用 i 表示当前输入后缀起点，j 表示当前模式后缀起点。当前模式不是星号组合时，只有当前字符相同或模式为点号，才能把两个位置都前进一步。定义当前字符是否兼容：

same(i,j)=[si=pj]∨[pj=dot]same(i,j) = [s_i = p_j] \vee [p_j = \text{dot}]

当模式下一字符是星号时，作者源码在当前字符兼容的前提下显式枚举三种递归分支：

  1. 消费当前输入字符并越过整个星号组合，表示前导项这一次就是最后一次。
  2. 消费当前输入字符但模式位置不动，表示前导项还可能继续重复。
  3. 输入位置不动、模式越过两格，表示前导项出现零次。
作者分支下一个状态语义
消费一次并越过x*str + 1, pattern + 2把当前字符视为该段最后一次
消费一次并保留x*str + 1, pattern继续允许同一前导项匹配更多字符
跳过整个x*str, pattern + 2让前导项出现零次
当前字符与星号前导项匹配时，作者源码显式枚举三种递归分支。

若 R(i,j) 表示两个后缀能否完整匹配，当前字符兼容且模式下一位是星号时，作者三分支可写成：

R(i,j)=R(i+1,j+2)∨R(i+1,j)∨R(i,j+2)R(i,j)=R(i+1,j+2) \vee R(i+1,j) \vee R(i,j+2)

第一分支在逻辑上是冗余的：第二分支消费一个字符并保留星号，下一层仍可选择第三分支越过星号，所以“两分支”实现也能覆盖恰好一次。不过忠实阅读作者源码时应认识三条路径各自语义，再说明为什么工程实现可以合并，而不是漏抄一条后宣称完全相同。

若当前字符不兼容，星号组合只能取零次，转到 R(i,j+2)。若没有星号，兼容时转到 R(i+1,j+1)，不兼容立即失败。每个递归分支至少推进输入位置或模式位置，因此合法有限输入最终会到达边界。

两个决定完整匹配

字符串和模式同时结束时返回 true。模式先结束而字符串未结束时返回 false。字符串先结束但模式未结束时不能立即失败，因为剩余模式可能全部由 x* 组合构成，例如空串与 cab* 匹配。

作者代码没有单独写“字符串先结束”的分支。它继续检查模式下一位是否为星号；若是，就不断取零次越过组合，最终到达双空成功。点号分支还额外要求输入当前字符不是结束符，避免点号错误消费空字符。

模式以星号开头或含连续星号不在作者测试契约中。源码读取 pattern 后一位是安全的，因为 C 字符串末尾还有结束符；但看到星号时默认它有合法前导项。生产接口应先验证模式：首位不能是星号，任一星号前一位不能也是星号。非法模式是返回 false 还是抛参数错误必须由 API 约定。

忠实递归与备忘录实现

下面使用字符串视图和下标复刻作者分支，并加入二维。缓存值 0 表示未知，1 表示失败，2 表示成功。为突出作者结构，星号兼容时仍保留三分支。

#include <cstdint>
#include <string_view>
#include <vector>
 
bool matchCore(std::string_view text,
               std::string_view pattern,
               std::size_t i,
               std::size_t j,
               std::vector<std::vector<std::uint8_t>>& memo) {
    auto& cached = memo[i][j];
    if (cached != 0) return cached == 2;
 
    bool result = false;
    if (j == pattern.size()) {
        result = i == text.size();
    } else {
        const bool currentMatches =
            i < text.size() &&
            (pattern[j] == '.' || pattern[j] == text[i]);
        const bool followedByStar =
            j + 1 < pattern.size() && pattern[j + 1] == '*';
 
        if (followedByStar) {
            if (currentMatches) {
                result =
                    matchCore(text, pattern, i + 1, j + 2, memo) ||
                    matchCore(text, pattern, i + 1, j, memo) ||
                    matchCore(text, pattern, i, j + 2, memo);
            } else {
                result = matchCore(text, pattern, i, j + 2, memo);
            }
        } else {
            result = currentMatches &&
                matchCore(text, pattern, i + 1, j + 1, memo);
        }
    }
 
    cached = result ? 2 : 1;
    return result;
}
 
bool fullMatch(std::string_view text, std::string_view pattern) {
    std::vector memo(
        text.size() + 1,
        std::vector<std::uint8_t>(pattern.size() + 1, 0));
    return matchCore(text, pattern, 0, 0, memo);
}

递归状态只由 i、j 决定，一共有 (M+1)(N+1) 种。备忘录让每种状态最多展开一次，时间和空间都是 O(MN)，递归栈最深 O(M+N)。不加缓存时，不同星号选择会反复抵达相同后缀，最坏搜索树指数增长。

aab 与 c*a*b：先跳过，再消费(aab, c*a*b)c*取零次(aab, a*b)a*消费a(ab, a*b)a*消费a(b, a*b)a*取零次(b, b)普通字符(空, 空)成功每条边至少缩短字符串或模式，递归最终到达边界
状态由两个后缀位置唯一确定，适合用二维备忘录消除重复搜索。

以 aab 与 cab 为例，先让 c* 取零次；a* 连续消费两个 a；再让 a* 结束；最后普通 b 与 b 同时消费。每一步都只依赖当前两个后缀，所以同一状态无论由哪条路径到达，其真假结果都相同，正适合缓存。

从后缀递归翻转为前缀动态规划

也可以定义 D[i][j]：输入前 i 个字符能否与模式前 j 个字符完整匹配。双空状态为真，非空输入与空模式为假：

D[0][0]=1,D[i][0]=0(i>0)D[0][0]=1, \qquad D[i][0]=0 \quad (i>0)

普通字符或点号要求当前字符兼容，并继承左上角状态：

D[i][j]=same(i−1,j−1)∧D[i−1][j−1]D[i][j]=same(i-1,j-1) \wedge D[i-1][j-1]

若模式第 j 个字符是星号，它修饰第 j-1 个字符。取零次时删除模式末尾两项，查看 D[i][j-2]；取一次或多次时，当前输入字符必须兼容前导项，并让星号继续匹配更短输入：

D[i][j]=D[i][j−2]∨(same(i−1,j−2)∧D[i−1][j])D[i][j]=D[i][j-2] \vee (same(i-1,j-2) \wedge D[i-1][j])

初始化空输入这一行时，a*、ab 等模式可以逐段取零次：模式当前位置为星号时令 D[0][j]=D[0][j-2]。其他空输入状态保持假。计算顺序按 i 从 0 到 M、j 从 1 到 N，使当前格依赖的左侧和上一行都已完成。

#include <string_view>
#include <vector>
 
bool fullMatchDp(std::string_view text, std::string_view pattern) {
    const std::size_t m = text.size();
    const std::size_t n = pattern.size();
    std::vector dp(m + 1, std::vector<bool>(n + 1, false));
    dp[0][0] = true;
 
    for (std::size_t j = 2; j <= n; ++j) {
        if (pattern[j - 1] == '*') {
            dp[0][j] = dp[0][j - 2];
        }
    }
 
    for (std::size_t i = 1; i <= m; ++i) {
        for (std::size_t j = 1; j <= n; ++j) {
            if (pattern[j - 1] != '*') {
                const bool same =
                    pattern[j - 1] == '.' ||
                    pattern[j - 1] == text[i - 1];
                dp[i][j] = same && dp[i - 1][j - 1];
            } else if (j >= 2) {
                const bool same =
                    pattern[j - 2] == '.' ||
                    pattern[j - 2] == text[i - 1];
                dp[i][j] =
                    dp[i][j - 2] ||
                    (same && dp[i - 1][j]);
            }
        }
    }
    return dp[m][n];
}

二维 DP 同样需要 O(MN) 时间和空间。每格只依赖上一行与当前行左侧，可以滚动成两行 O(N) 空间；但星号的 D[i][j-2]来自正在构造的当前行，更新顺序必须从左到右。若强行单数组原地更新，还要保存被覆盖的左上角旧值，代码更易错。

作者30组测试锁定哪些边界

官方源码从空串开始，逐渐增加普通字符、点号、星号和多个星号段，共有30组断言。空串与空模式、空串与 .、空串与 .、空串与 c 四组首先锁定终止规则和星号零次。单字符 a 再分别与 .、a.、空模式、点号和 ab 比较，锁定完整匹配。

中段测试 aa、ab、aaa，覆盖星号消费一次、多次、点号消费恰好一次以及普通字符不匹配。后段的 cab、abac*a、.aa 迫使算法在多个零次与多次选择间回溯，可发现只走贪心路径或漏写分支的错误。

值得注意的是作者 Test15 和 Test16 都是 ab 与 .*，属于重复测试。忠实清单应保留它们确实存在这一事实，但工程套件可以补充更有区分度的用例，例如换行字符契约、非法模式、长重复前缀和备忘录性能。

#include <cassert>
#include <utility>
#include <vector>
 
void testRegularExpressions() {
    const std::vector<std::pair<std::pair<const char*, const char*>, bool>> cases{
        {{{"", ""}}, true},
        {{{"", ".*"}}, true},
        {{{"", "."}}, false},
        {{{"", "c*"}}, true},
        {{{"a", "ab*"}}, true},
        {{{"aa", "a*"}}, true},
        {{{"aaa", "a.a"}}, true},
        {{{"aaa", "ab*a"}}, false},
        {{{"aab", "c*a*b"}}, true},
        {{{"aaca", "ab*a*c*a"}}, true},
        {{{"aaba", "ab*a*c*a"}}, false},
        {{{"bbbba", ".*a*a"}}, true},
        {{{"bcbbabab", ".*a*a"}}, false},
    };
 
    for (const auto& [input, expected] : cases) {
        assert(fullMatch(input.first, input.second) == expected);
        assert(fullMatchDp(input.first, input.second) == expected);
    }
}

实际提交应把作者30组全部逐项移植，并让递归备忘录版与 DP 版交叉校验。还要构造长输入 aaaaa...b 与模式 aaa*...c：朴素递归会产生巨大搜索树，优化版应在状态数上界内稳定结束。性能测试必须限制输入规模，避免把无缓存版本拖垮整个测试进程。

正确性与复杂度证明

递归正确性可按剩余模式长度归纳。普通项只有一种合法消费方式；星号项的合法匹配按重复次数分为零次和至少一次，两类互斥且覆盖全部可能。作者把至少一次再分为“本次结束”和“还会继续”，仍然覆盖同一集合。每个分支推进位置，最终边界准确判断完整消费。

DP 是同一分类的反向计算。D[i][j-2]覆盖星号前导项零次，same 与 D[i-1][j]覆盖至少一次；普通项取左上角。状态按依赖顺序填表，所以由更短前缀正确性可推出当前前缀正确，最终 D[M][N]就是整串答案。

备忘录与 DP 的状态数量均为 (M+1)(N+1)，每状态只做常数次判断，因此时间 O(MN)。二维表空间 O(MN)；递归另有 O(M+N) 调用栈，滚动 DP 可把表空间降到 O(N)。模式验证本身线性，不改变总复杂度。

工程上还要明确字符单位。按字节遍历 UTF-8 时，点号匹配的是一个字节而非一个 Unicode 字符；若接口承诺按字符匹配，应先解码为码点或使用成熟正则引擎。本题作者使用 char，讨论的是窄字符序列，不能直接推广到所有文本语义。

本章练习

练习

问题 1： 完整匹配与子串匹配的区别是什么？

问题 2： 星号的两种分支各处理什么情况？

问题 3： 递归匹配如何避免重复计算？

本章回顾

  1. 正则表达式匹配要求模式消费整个输入，不是搜索任意子串。
  2. 点号匹配任意一个非空字符，星号表示前一字符出现零次或多次。
  3. 作者在星号兼容时显式写了消费后越过、消费后保留、零次跳过三条递归分支。
  4. 两分支写法可把“恰好一次”并入消费后保留再跳过，但必须证明等价。
  5. 双空成功；模式先结束失败；字符串先结束仍可能被剩余星号段匹配。
  6. 备忘录和二维 DP 都把指数回溯降为 O(MN) 状态计算。
  7. 非法首星号、连续星号、UTF-8字符单位和长输入是工程接口额外边界。
  8. 作者30组测试锁定空串、点号、星号零次/多次和多段回溯语义。

名词解释

名词解释

本章出现的专业名词，用大白话再讲一遍。

完整匹配
模式覆盖字符串全部字符，两者同时到达末尾。
星号
前一字符出现零次或多次的通配符。
终止条件
字符串和模式为空或星号的分支结束条件。
复习本章（10 题）

讨论

评论区加载中…