0010. Regular Expression Matching¶
题目信息¶
- 题号:
正则表达式匹配
- 难度:
Hard
- 主题:
字符串、递归、记忆化、动态规划
- 原题:
- 重点:
从枚举星号重复次数,推导到后缀状态转移,再压缩动态规划的行状态
题目重述¶
给定字符串 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++ 实现¶
#include <string>
#include <vector>
class Solution {
private:
bool firstMatches(const std::string& s, const std::string& p, int i, int j) {
return i < static_cast<int>(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<int>(p.size())) {
return i == static_cast<int>(s.size());
}
const bool first = firstMatches(s, p, i, j);
if (j + 1 < static_cast<int>(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<std::vector<int>>& memo) {
int& cached = memo[i][j];
if (cached != -1) {
return cached == 1;
}
bool answer = false;
if (j == static_cast<int>(p.size())) {
answer = i == static_cast<int>(s.size());
} else {
const bool first = firstMatches(s, p, i, j);
if (j + 1 < static_cast<int>(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<std::vector<int>> memo(s.size() + 1, std::vector<int>(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<int>(s.size());
const int n = static_cast<int>(p.size());
std::vector<std::vector<char>> dp(m + 1, std::vector<char>(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<int>(s.size());
const int n = static_cast<int>(p.size());
std::vector<char> 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<char> 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" 为例:
状态 |
模式起点 |
选择 |
后继状态 |
|---|---|---|---|
|
|
|
|
|
|
消费第一个 |
|
|
|
再消费一个 |
|
|
|
|
|
|
|
同时消费字符和模式 |
|
最终状态 (3, 5) 的两个后缀都为空,因此整条匹配路径成功。星号每一步只做“退出分组”或“消费一个
并保留分组”两种选择,已经覆盖所有重复次数。
代码演进¶
directDfs 直接枚举星号分支,代码最接近匹配语义,瓶颈是不同路径反复计算相同后缀。
memoizedDfs 增加二维缓存,每个 (i, j) 只展开一次,指数级搜索被压缩为有限状态图。
bottomUp 删除递归调用和递归栈,按依赖方向显式填充全部后缀状态。
compressedDp 观察到当前行只依赖自身右侧与下一行,删除完整二维表,只保留两个模式长度的一维数组。
公开入口采用这一方案。
复杂度分析¶
方法 |
时间复杂度 |
工作空间 |
主要代价 |
|---|---|---|---|
朴素递归 |
最坏指数级 |
|
重复展开相同后缀状态 |
记忆化递归 |
|
|
保存全部状态,并使用递归栈 |
二维动态规划 |
|
|
填充完整后缀状态表 |
一维动态规划 |
|
|
每次只保存当前行和下一行 |
其中 m 和 n 分别是字符串与模式长度。每个动态规划状态只执行常数次比较和布尔运算。
边界处理¶
模式耗尽时,字符串也必须耗尽,体现完整匹配而非子串匹配;
字符串后缀为空时,剩余模式只有全部由可取零次的星号分组组成才可能成功;
.仍然必须消费一个真实字符,不能匹配空字符串;*的零次分支跳过两个模式字符,重复分支只推进字符串位置;模式由题目保证合法,代码不负责修复缺少前置元素的
*。