递归易栈溢出因匹配任意长度导致分叉爆炸，需记忆化、预处理连续、早判边界；DP转移为dpi=dpi||(i>0&&dpi-1)，注意空串、?消耗字符、UTF-8编码等边界。
为什么递归直接写容易栈溢出
通配符匹配里 * 可以匹配任意长度子串，递归时若不加剪枝，遇到 "*"*100 和长目标串会疯狂分叉。比如 s = "a"*1000、p = "*a*a*a*"，朴素递归可能尝试上万条路径，每次调用都压栈，很快触发 stack overflow。
实操建议：
- 加记忆化：用
memo[i][j]缓存s.substr(i)和p.substr(j)是否匹配过，状态维度是s.length() × p.length() - 优先处理连续
*：预处理模式串，把"**"替换成"*"，避免等价分支重复计算 - 递归基要早判：一旦
j == p.length()，立刻返回i == s.length()；不要等到最后才检查
动态规划填表时 * 的转移逻辑怎么写
dp[i][j] 表示 s[0..i-1] 和 p[0..j-1] 是否匹配。关键在 p[j-1] == '*' 时的转移——它不消耗 s 字符，但可以“跳过”或“吃掉”一个字符。
正确转移是：dp[i][j] = dp[i][j-1] || (i > 0 && dp[i-1][j])。
立即学习“C++免费学习笔记（深入）”；
说明：
-
dp[i][j-1]：*匹配空串（跳过） -
dp[i-1][j]：*匹配至少一个字符（吃掉s[i-1]后继续用同一个*） - 不能写成
dp[i-1][j-1]——那相当于把*当成普通字符用了 - 初始化：
dp[0][0] = true；dp[0][j]依赖前面是否全是*，需单独循环处理
边界 case 容易漏掉的三个点
实际调试中最常卡住的不是主逻辑，而是这些边界：
-
s为空但p非空：只有当p全是*时才匹配，比如""vs"***"→ true，但""vs"a*"→ false -
?遇到空s：直接失败，?必须消耗一个字符，不能跳过 - 输入含非 ASCII 字符：C++ 默认
string是字节序列，如果传入 UTF-8 编码的中文，?会按字节而非 Unicode 字符匹配，导致误判。生产环境应先确认编码或改用std::u8string
性能差异：DP 比记忆化递归快在哪
两者时间复杂度都是 O(m×n)，但 DP 实际更快，因为：
- 无函数调用开销：避免了递归进出栈、参数拷贝（尤其是
string传值） - 内存局部性好：二维数组按行连续访问，CPU 缓存友好；而记忆化递归的
map或unordered_map查找有哈希冲突和指针跳转 - 可空间压缩：DP 只依赖上一行和当前行，能从
O(m×n)降到O(n)，而记忆化递归很难压缩状态
不过 DP 要注意初始化顺序——必须按行优先填表，且 i 和 j 都从 0 开始，错一步整个表就废。
