0044. Wildcard Matching¶
题目信息¶
- 题号:
通配符匹配
- 难度:
Hard
- 主题:
字符串、递归、记忆化搜索、动态规划
- 原题:
- 重点:
从星号长度枚举产生的重复状态,推导到二维前缀状态,并按依赖方向压缩为一维数组
题目重述¶
给定字符串 s 和模式 p,判断模式能否匹配整个字符串。
模式中的字符具有以下含义:
普通小写字母只能匹配相同字母;
?恰好匹配任意一个字符;*可以匹配任意长度的字符序列,包括空序列。
只有字符串和模式都被完整消费时才算匹配成功,不能只匹配字符串中的某个子串。
s 和 p 的长度均位于 [0, 2000]。s 只含小写英文字母,p 只含小写英文字母、?
和 *。
自建示例¶
星号匹配多个字符:
输入:s = "cabxy", p = "c*?y"
输出:true
解释:c 匹配 c,* 匹配 "ab",? 匹配 x,y 匹配 y。
星号匹配空串:
输入:s = "ab", p = "a*b"
输出:true
解释:* 可以不消费任何字符。
模式仍有字符未消费:
输入:s = "abcd", p = "a*d?"
输出:false
解释:d 匹配字符串末位后,模式中的 ? 已经没有字符可以匹配。
空字符串边界:
输入:s = "", p = "***"
输出:true
解释:每个 * 都取空串;若模式中含普通字符或 ?,结果则为 false。
C++ 实现¶
#include <string>
#include <vector>
class Solution {
private:
bool backtrack(
const std::string& s,
const std::string& p,
int stringIndex,
int patternIndex
) {
if (patternIndex == static_cast<int>(p.size())) {
return stringIndex == static_cast<int>(s.size());
}
if (p[patternIndex] == '*') {
const bool matchEmpty = backtrack(
s,
p,
stringIndex,
patternIndex + 1
);
const bool matchOneMore =
stringIndex < static_cast<int>(s.size()) &&
backtrack(s, p, stringIndex + 1, patternIndex);
return matchEmpty || matchOneMore;
}
if (stringIndex == static_cast<int>(s.size())) {
return false;
}
if (p[patternIndex] != '?' && p[patternIndex] != s[stringIndex]) {
return false;
}
return backtrack(s, p, stringIndex + 1, patternIndex + 1);
}
bool plainRecursive(const std::string& s, const std::string& p) {
return backtrack(s, p, 0, 0);
}
bool memoDfs(
const std::string& s,
const std::string& p,
int stringIndex,
int patternIndex,
std::vector<std::vector<int>>& memo
) {
int& cached = memo[stringIndex][patternIndex];
if (cached != -1) {
return cached == 1;
}
bool answer = false;
if (patternIndex == static_cast<int>(p.size())) {
answer = stringIndex == static_cast<int>(s.size());
} else if (p[patternIndex] == '*') {
answer = memoDfs(
s,
p,
stringIndex,
patternIndex + 1,
memo
);
if (!answer && stringIndex < static_cast<int>(s.size())) {
answer = memoDfs(
s,
p,
stringIndex + 1,
patternIndex,
memo
);
}
} else if (
stringIndex < static_cast<int>(s.size()) &&
(p[patternIndex] == '?' || p[patternIndex] == s[stringIndex])
) {
answer = memoDfs(
s,
p,
stringIndex + 1,
patternIndex + 1,
memo
);
}
cached = answer ? 1 : 0;
return answer;
}
bool memoizedSearch(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 twoDimensionalDp(const std::string& s, const std::string& p) {
const int stringLength = static_cast<int>(s.size());
const int patternLength = static_cast<int>(p.size());
std::vector<std::vector<char>> dp(
stringLength + 1,
std::vector<char>(patternLength + 1, false)
);
dp[0][0] = true;
for (int patternSize = 1; patternSize <= patternLength; ++patternSize) {
if (p[patternSize - 1] == '*') {
dp[0][patternSize] = dp[0][patternSize - 1];
}
}
for (int stringSize = 1; stringSize <= stringLength; ++stringSize) {
for (int patternSize = 1;
patternSize <= patternLength;
++patternSize) {
const char patternChar = p[patternSize - 1];
if (patternChar == '*') {
dp[stringSize][patternSize] =
dp[stringSize][patternSize - 1] ||
dp[stringSize - 1][patternSize];
} else if (
patternChar == '?' ||
patternChar == s[stringSize - 1]
) {
dp[stringSize][patternSize] =
dp[stringSize - 1][patternSize - 1];
}
}
}
return dp[stringLength][patternLength];
}
bool oneDimensionalDp(const std::string& s, const std::string& p) {
const int patternLength = static_cast<int>(p.size());
std::vector<char> dp(patternLength + 1, false);
dp[0] = true;
for (int patternSize = 1; patternSize <= patternLength; ++patternSize) {
dp[patternSize] =
p[patternSize - 1] == '*' && dp[patternSize - 1];
}
for (char stringChar : s) {
char diagonal = dp[0];
dp[0] = false;
for (int patternSize = 1;
patternSize <= patternLength;
++patternSize) {
const char above = dp[patternSize];
const char patternChar = p[patternSize - 1];
if (patternChar == '*') {
dp[patternSize] =
dp[patternSize] || dp[patternSize - 1];
} else {
dp[patternSize] =
diagonal &&
(patternChar == '?' || patternChar == stringChar);
}
diagonal = above;
}
}
return dp[patternLength];
}
public:
bool isMatch(std::string s, std::string p) {
return oneDimensionalDp(s, p);
}
};
题解¶
后缀递归状态¶
令 match(i, j) 表示字符串后缀 s[i:] 能否与模式后缀 p[j:] 完整匹配。模式已经结束时,只有字符串也
恰好结束才能返回真。
普通字符和 ? 都必须消费一个字符串字符,并把两个下标同时加一。普通字符还要求两者相等;若字符串已经结束,
这两类模式字符都无法继续匹配。
星号分支¶
* 的匹配长度未知,但所有长度都能由两个动作组成:
match(i, j + 1) 当前 * 匹配空串
match(i + 1, j) 当前 * 再匹配一个字符
第二个动作保留模式下标 j,因此可以连续发生,覆盖 * 匹配一个、两个或更多字符。任意合法匹配中的当前
* 要么长度为零,要么至少消费一个字符,所以两个分支覆盖全部可能;每个动作也都严格遵守通配符语义。
重复状态¶
不同星号之间可以用多种方式分配字符,却重新到达同一对下标 (i, j)。直接递归会重复展开相同后缀搜索树,最坏
呈指数增长。
状态只由两个下标决定,总数至多为 (m + 1)(n + 1)。memoizedSearch 缓存每个状态的真假结果,使每个
match(i, j) 至多求解一次,将时间降为 O(mn)。
前缀动态规划¶
把同一状态图改为自底向上计算:
dp[i][j] = s 的前 i 个字符能否与 p 的前 j 个字符完整匹配
dp[0][0] 为真。普通字符或 ? 匹配当前字符后,剩余问题就是两个前缀都去掉末位:
dp[i][j] = dp[i - 1][j - 1]
前提是 p[j - 1] 为 ?,或它等于 s[i - 1]。
对于 *,递归中的两个动作直接变为两个前缀状态:
dp[i][j - 1] * 匹配空串
dp[i - 1][j] * 匹配当前字符,并继续保留使用权
因此:
dp[i][j] = dp[i][j - 1] || dp[i - 1][j]
第二项可以沿同一列向下传播,使一个星号匹配任意多个字符。最终答案是 dp[m][n],因为只有该状态同时消费完整
字符串与完整模式。
边界初始化¶
空模式只能匹配空字符串,所以 dp[i][0] 在 i > 0 时均为假。空字符串只能由模式前缀中的全部星号匹配:
dp[0][j] = dp[0][j - 1] && p[j - 1] == '*'
连续星号无需合并,真值会在第一行逐个向右传播。若模式前缀中出现普通字符或 ?,后续状态都保持为假。
这组初始化也自然覆盖两个边界:s 为空时直接读取第一行末端;p 为空而 s 非空时,第一列始终为假。
一维压缩¶
二维转移只依赖三个方向:当前行左侧、上一行同列和上一行左上角。用一维数组从左向右更新时:
更新前的
dp[j]是上一行同列;更新后的
dp[j - 1]是当前行左侧;diagonal保存上一行左上角。
于是星号使用 dp[j] || dp[j - 1],普通字符与 ? 使用 diagonal。更新当前格之前先保存原
dp[j],再把它交给下一列作为新的 diagonal。
从左向右的顺序不能颠倒:星号转移需要当前行已经计算出的左侧状态;若从右向左更新,dp[j - 1] 仍属于上一行。
每处理一个字符串字符,还要把 dp[0] 设为假,因为非空字符串不能由空模式匹配。
状态演化¶
对 s = "ab"、p = "*?b",数组下标表示模式前缀长度:
已处理字符串前缀 |
|
|
|
|
|---|---|---|---|---|
|
真 |
真 |
假 |
假 |
|
假 |
真 |
真 |
假 |
|
假 |
真 |
真 |
真 |
第一行中星号匹配空串。处理 a 后,? 从左上角真值转移;处理 b 后,末尾普通字符再次从左上角转移,
最终右下角为真。
代码演进¶
plainRecursive 直接枚举星号匹配空串或继续吞字符,完整表达匹配语义,但反复计算相同下标状态。
memoizedSearch 保存后缀状态,将搜索树压缩为有限状态图。twoDimensionalDp 改用前缀状态,自底向上计算同一组
依赖关系。oneDimensionalDp 再利用每格只依赖三个方向,将表格压缩为一行;公开入口采用该方法。
复杂度分析¶
设字符串长度为 m,模式长度为 n。
直接递归最坏会反复分配星号长度,时间呈指数增长,递归深度为
O(m + n);记忆化搜索访问至多
(m + 1)(n + 1)个状态,时间和缓存空间均为O(mn);二维动态规划时间为
O(mn),表格空间为O(mn);一维动态规划仍执行相同数量的转移,时间为
O(mn),额外空间降为O(n)。