C++实现带有通配符的字符串匹配 _ 递归与动态规划思路【源码】-C++-PHP中文网

ismatch递归易栈溢出因“”导致指数级分支，如“a”配“aaa”时每个“”尝试多长度匹配；应加记忆化、提前剪枝、避免裸或逻辑，并用dpi表示s[0..i-1]与p[0..j-1]匹配，注意“*”转移需按行正向填表。

c++实现带有通配符的字符串匹配 _ 递归与动态规划思路【源码】

通配符匹配里最耗资源的是 "*"，它能匹配任意长度子串（包括空串），递归分支呈指数爆炸。比如模式 "********a" 配字符串 "aaa"，每个 "*" 都会尝试“匹配 0 个、1 个、2 个……”直到失败回溯，实际调用深度远超字符串长度。

实操建议：

加记忆化——用 memo[i][j] 记录 s[i:] 和 p[j:] 是否已算过，避免重复递归
提前剪枝：若 p[j] 是 "*"，先递归跳过它（即 "*" 匹配空串），再递归让它吃掉 s[i] 后继续——不要用 for 循环枚举吃几个字符
别直接写 return isMatch(s, p, i+1, j) || isMatch(s, p, i, j+1) 这类裸或逻辑，C++ 短路求值虽存在，但编译器未必优化掉冗余调用；显式拆成 if 判断更可控

动态规划里最容易错的是状态含义和数组下标偏移。推荐统一用 dp[i][j] 表示 s[0..i-1]（前 i 个字符）能否被 p[0..j-1]（前 j 个字符）匹配，这样空字符串对应 i=0 或 j=0，边界自然清晰。

关键初始化细节：

dp[0][0] = true：空串匹配空模式
dp[0][j]（j > 0）：只有当 p[j-1] 是 "*" 且 dp[0][j-1] 为 true 时才可能为 true——因为 "*" 是唯一能匹配空串的非空模式
dp[i][0]（i > 0）恒为 false：非空串无法被空模式匹配

错误常见于把 dp[i][j] 定义成 “以 i、j 结尾”，导致初始化混乱或循环越界。

"?" 和 "*" 看似都是通配，但状态转移完全不同："?" 是确定性跳转，"*" 是不确定性分叉。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

具体到 dp[i][j] 更新：

若 p[j-1] == '?'：必须消耗一个字符，dp[i][j] = dp[i-1][j-1]
若 p[j-1] == '*'：两种选择——“不吃字符”（dp[i][j-1]）或“吃一个并继续留着它”（dp[i-1][j]），即 dp[i][j] = dp[i][j-1] || dp[i-1][j]
若 p[j-1] 是普通字符：仅当 s[i-1] == p[j-1] 且 dp[i-1][j-1] 为 true 时成立

注意："*" 的转移依赖 dp[i-1][j]，所以内层循环必须按行（i）顺序填表，不能按列；否则 dp[i-1][j] 还没算就用了。

从二维 dp[i][j] 压到一维 dp[j] 是可行的，但必须保留整行，不能只记上一行和当前行的几个值。原因在于 "*" 的转移要同时访问 dp[j-1]（左边）和 dp[j]（上方，即上一轮 i-1 时的值）。

实操要点：

用单数组 vector<bool> dp(m+1)</bool>，其中 m = p.length()
外层遍历 i（s 的位置），内层从 j = 1 到 m 正向遍历——保证更新 dp[j] 时，dp[j-1] 是本轮新值（对应 dp[i][j-1]），而旧的 dp[j] 还是上轮值（对应 dp[i-1][j]）
不能反向遍历，否则 dp[j] 被覆盖后，dp[j+1] 就拿不到正确的上轮值了