0010. Regular Expression Matching
=================================
题目信息
--------
:题号: 0010. 正则表达式匹配
:难度: Hard
:主题: 字符串、递归、记忆化、动态规划
:原题: `LeetCode 0010 `_
:重点: 从枚举星号重复次数,推导到后缀状态转移,再压缩动态规划的行状态
题目重述
--------
给定字符串 ``s`` 和模式 ``p``,判断模式能否匹配字符串的全部字符。
模式只包含小写英文字母、``.`` 和 ``*``:
* 小写字母只匹配与自身相同的一个字符;
* ``.`` 匹配任意一个字符;
* ``*`` 修饰它前面的模式元素,表示该元素可以连续出现零次或多次。
``*`` 不是独立通配符。匹配必须覆盖整个字符串,不能只匹配其中一段。字符串和模式长度都位于
``[1, 20]``,字符串只包含小写英文字母;题目保证每个 ``*`` 前都有可修饰的有效元素。
自建示例
--------
* 普通字符不足:``s = "aa"``、``p = "a"``,模式只消费一个字符,返回 ``false``;
* 星号重复多次:``s = "miss"``、``p = "mis*"``,``s*`` 消费两个 ``s``,返回 ``true``;
* 星号选择零次:``s = "b"``、``p = "a*b"``,``a*`` 不消费字符,返回 ``true``;
* 点号与星号组合:``s = "ab"``、``p = ".*"``,``.*`` 可以消费全部字符,返回 ``true``;
* 多组星号分配:``s = "aab"``、``p = "c*a*b"``,``c*`` 取零次、``a*`` 取两次,返回 ``true``;
* 完整匹配失败:``s = "cab"``、``p = "c.*d"``,末尾 ``d`` 无法匹配,返回 ``false``。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
bool firstMatches(const std::string& s, const std::string& p, int i, int j) {
return i < static_cast(s.size()) && (p[j] == s[i] || p[j] == '.');
}
bool directDfs(const std::string& s, const std::string& p, int i, int j) {
if (j == static_cast(p.size())) {
return i == static_cast(s.size());
}
const bool first = firstMatches(s, p, i, j);
if (j + 1 < static_cast(p.size()) && p[j + 1] == '*') {
return directDfs(s, p, i, j + 2) || (first && directDfs(s, p, i + 1, j));
}
return first && directDfs(s, p, i + 1, j + 1);
}
bool memoDfs(const std::string& s, const std::string& p, int i, int j,
std::vector>& memo) {
int& cached = memo[i][j];
if (cached != -1) {
return cached == 1;
}
bool answer = false;
if (j == static_cast(p.size())) {
answer = i == static_cast(s.size());
} else {
const bool first = firstMatches(s, p, i, j);
if (j + 1 < static_cast(p.size()) && p[j + 1] == '*') {
answer = memoDfs(s, p, i, j + 2, memo) ||
(first && memoDfs(s, p, i + 1, j, memo));
} else {
answer = first && memoDfs(s, p, i + 1, j + 1, memo);
}
}
cached = answer ? 1 : 0;
return answer;
}
bool memoizedDfs(const std::string& s, const std::string& p) {
std::vector> memo(s.size() + 1, std::vector(p.size() + 1, -1));
return memoDfs(s, p, 0, 0, memo);
}
bool bottomUp(const std::string& s, const std::string& p) {
const int m = static_cast(s.size());
const int n = static_cast(p.size());
std::vector> dp(m + 1, std::vector(n + 1, false));
dp[m][n] = true;
for (int i = m; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
const bool first = i < m && (p[j] == s[i] || p[j] == '.');
if (j + 1 < n && p[j + 1] == '*') {
dp[i][j] = dp[i][j + 2] || (first && dp[i + 1][j]);
} else {
dp[i][j] = first && dp[i + 1][j + 1];
}
}
}
return dp[0][0];
}
bool compressedDp(const std::string& s, const std::string& p) {
const int m = static_cast(s.size());
const int n = static_cast(p.size());
std::vector next(n + 1, false);
next[n] = true;
for (int j = n - 2; j >= 0; --j) {
if (p[j + 1] == '*') {
next[j] = next[j + 2];
}
}
for (int i = m - 1; i >= 0; --i) {
std::vector current(n + 1, false);
for (int j = n - 1; j >= 0; --j) {
const bool first = p[j] == s[i] || p[j] == '.';
if (j + 1 < n && p[j + 1] == '*') {
current[j] = current[j + 2] || (first && next[j]);
} else {
current[j] = first && next[j + 1];
}
}
next.swap(current);
}
return next[0];
}
public:
bool isMatch(std::string s, std::string p) {
return compressedDp(s, p);
}
};
题解
----
原始分支
~~~~~~~~
没有 ``*`` 时,匹配过程只有一条路径:当前模式元素与当前字符匹配后,两边同时前进一步。
``*`` 使一个模式元素可以消费零个、一个或多个字符,算法必须决定每一组星号实际消费多少字符。
最直接的方法是从字符串下标 ``i`` 和模式下标 ``j`` 开始递归尝试。真正影响后续结果的不是此前采用了
哪些分支,而只是两个尚未处理的后缀,因此定义:
``match(i, j)`` 表示 ``s[i:]`` 能否被 ``p[j:]`` 完整匹配。
当 ``j`` 到达模式末尾时,只有 ``i`` 也到达字符串末尾才成功。字符串先耗尽时不能立即失败,因为剩余
模式可能由 ``a*b*c*`` 这类可以全部取零次的分组组成。
普通元素
~~~~~~~~
当前位置能够消费一个字符的条件为
``first = i < s.size() && (p[j] == s[i] || p[j] == '.')``。
若当前模式元素后面没有 ``*``,它必须恰好消费一个字符。只有 ``first`` 为真时,状态才能同时移动到
``(i + 1, j + 1)``。字母和 ``.`` 的差异只体现在 ``first`` 的计算中,后续转移完全相同。
星号转移
~~~~~~~~
若 ``p[j + 1] == '*'``,当前分组只有两种本质不同的选择:
* 出现零次:不消费字符串,跳过模式中的 ``元素 + *``,进入 ``(i, j + 2)``;
* 出现至少一次:先消费一个匹配字符,模式仍停在当前元素,进入 ``(i + 1, j)``。
第二条分支保留 ``j``,所以下一状态仍可继续消费或改选零次退出。它由此覆盖一次、两次以及更多次,
不需要单独枚举具体重复次数。转移统一为
``match(i, j) = match(i, j + 2) || (first && match(i + 1, j))``。
``directDfs`` 完整实现了这棵选择树。连续星号会产生大量不同的消费分配,例如 ``s = "aaaa"``、
``p = "a*a*"`` 中,多条路径会到达同一个 ``(i, j)``,因此朴素递归可能产生指数级重复计算。
后缀记忆
~~~~~~~~
``memoizedDfs`` 为每个 ``(i, j)`` 保存未计算、失败和成功三种状态。第一次进入一个后缀问题时展开递归,
之后再次到达同一状态时直接返回缓存结果。
字符串共有 ``m + 1`` 个后缀起点,模式共有 ``n + 1`` 个后缀起点,所以最多只有
``(m + 1)(n + 1)`` 个不同状态。记忆化没有改变递归转移,只删除了不同匹配路径对同一后缀的重复展开。
自底向上
~~~~~~~~
二维动态规划使用相同定义:``dp[i][j]`` 表示 ``s[i:]`` 与 ``p[j:]`` 是否完整匹配。基础状态
``dp[m][n] = true`` 表示两个后缀同时为空。
当前状态依赖 ``dp[i][j + 2]``、``dp[i + 1][j]`` 或 ``dp[i + 1][j + 1]``,所以 ``i`` 和 ``j``
都从大到小遍历。计算一个格子时,它右侧、下一行和右下方的状态已经得到结果。
当 ``i == m`` 时,``first`` 必定为假,普通模式元素不能再消费字符;星号分组仍可通过
``dp[m][j + 2]`` 选择零次。因此空字符串后缀无需单独写一套转移规则。
空间压缩
~~~~~~~~
计算第 ``i`` 行时只会读取当前行右侧的 ``dp[i][j + 2]``,以及下一行的 ``dp[i + 1][j]`` 和
``dp[i + 1][j + 1]``。更早的行不会再被使用,因此二维表可以压缩为两个一维数组:
* ``next[j]`` 保存下一行 ``dp[i + 1][j]``;
* ``current[j]`` 保存正在计算的 ``dp[i][j]``。
模式下标仍从右向左扫描,使 ``current[j + 2]`` 在使用前已经计算。完成一行后交换两个数组,旧的
``current`` 不再需要。
开始处理真实字符前,``next`` 先表示空字符串后缀 ``dp[m][j]``。只有形如 ``元素*`` 的连续分组可以
取零次并最终到达 ``dp[m][n]``,所以初始化同样从右向左传播 ``next[j + 2]``。
状态推演
~~~~~~~~
以 ``s = "aab"``、``p = "c*a*b"`` 为例:
.. list-table::
:header-rows: 1
* - 状态
- 模式起点
- 选择
- 后继状态
* - ``(0, 0)``
- ``c*``
- ``c`` 不匹配 ``a``,只能取零次
- ``(0, 2)``
* - ``(0, 2)``
- ``a*``
- 消费第一个 ``a``
- ``(1, 2)``
* - ``(1, 2)``
- ``a*``
- 再消费一个 ``a``
- ``(2, 2)``
* - ``(2, 2)``
- ``a*``
- ``b`` 不匹配 ``a``,结束重复
- ``(2, 4)``
* - ``(2, 4)``
- ``b``
- 同时消费字符和模式
- ``(3, 5)``
最终状态 ``(3, 5)`` 的两个后缀都为空,因此整条匹配路径成功。星号每一步只做“退出分组”或“消费一个
并保留分组”两种选择,已经覆盖所有重复次数。
代码演进
~~~~~~~~
``directDfs`` 直接枚举星号分支,代码最接近匹配语义,瓶颈是不同路径反复计算相同后缀。
``memoizedDfs`` 增加二维缓存,每个 ``(i, j)`` 只展开一次,指数级搜索被压缩为有限状态图。
``bottomUp`` 删除递归调用和递归栈,按依赖方向显式填充全部后缀状态。
``compressedDp`` 观察到当前行只依赖自身右侧与下一行,删除完整二维表,只保留两个模式长度的一维数组。
公开入口采用这一方案。
复杂度分析
~~~~~~~~~~
.. list-table::
:header-rows: 1
* - 方法
- 时间复杂度
- 工作空间
- 主要代价
* - 朴素递归
- 最坏指数级
- ``O(m + n)``
- 重复展开相同后缀状态
* - 记忆化递归
- ``O(mn)``
- ``O(mn)``
- 保存全部状态,并使用递归栈
* - 二维动态规划
- ``O(mn)``
- ``O(mn)``
- 填充完整后缀状态表
* - 一维动态规划
- ``O(mn)``
- ``O(n)``
- 每次只保存当前行和下一行
其中 ``m`` 和 ``n`` 分别是字符串与模式长度。每个动态规划状态只执行常数次比较和布尔运算。
边界处理
~~~~~~~~
* 模式耗尽时,字符串也必须耗尽,体现完整匹配而非子串匹配;
* 字符串后缀为空时,剩余模式只有全部由可取零次的星号分组组成才可能成功;
* ``.`` 仍然必须消费一个真实字符,不能匹配空字符串;
* ``*`` 的零次分支跳过两个模式字符,重复分支只推进字符串位置;
* 模式由题目保证合法,代码不负责修复缺少前置元素的 ``*``。