京公网安备11010502063487号给定一个字符串 s 和一个含有通配符的模式 p：? 匹配任意单个字符，* 匹配任意长度的字符串（包括空串），判断整个 s 是否被 p 完全匹配。它常见的解法是动态规划，O(nm) 时间和空间。还有一种贪心加回退的双指针做法，只用 O(1) 额外空间：遇到 * 先让它匹配空串，记下位置，以后失配就回到最近的 *，让它多吃 s 的一个字符。这道题很适合展示"不带记忆化的递归"有多慢。本文用真实的调用次数展示指数爆炸，实测贪心和记忆化递归的耗时，给出五种语言的实现，并把贪心的匹配和回退做成分步演示。
完整题目见官方页面（链接在文末）。基准解是带记忆化的递归（lru_cache），逐个分情况：模式为空、当前是 *、当前是 ? 或普通字符，是与贪心完全不同的写法。一共 18 组用例，覆盖：官方示例、空串与空模式、只有 *、连续多个 *、模式比字符串长：
输入 ["aa","a"] 输出 false 输入 ["aa","*"] 输出 true 输入 ["cb","?a"] 输出 false 输入 ["adceb","*a*b"] 输出 true 输入 ["acdcb","a*c?b"] 输出 false 输入 ["",""] 输出 true
最直接的递归是：遇到 * 时有两种选择，让它匹配空串，或者让它吃掉 s 的一个字符，然后继续。同一个（s 的位置，p 的位置）状态会被重复计算很多次。我用 s 全是 a、模式是 *a*a*…*b 的最坏情形（永远匹配不上），统计不带记忆化的递归的真实调用次数：
s = a*n，p = *a*a*...*b（k 个 a）：不带记忆化的递归调用次数 vs 贪心的循环次数（贪心没有额外开销，用总步数计） n=10, k=3: 递归调用 1122 次（ 0.1 ms），结果 False；solve -> False n=14, k=4: 递归调用 9886 次（ 1.1 ms），结果 False；solve -> False n=18, k=5: 递归调用 87590 次（ 9.0 ms），结果 False；solve -> False n=22, k=6: 递归调用 781310 次（ 81.4 ms），结果 False；solve -> False
n 和模式里 a 的个数 k 每次各增加一点（n 加 4，k 加 1），递归调用次数却每次约乘 9：1122、9886、87590、781310，耗时从 0.1ms 涨到 81.8ms。规模再大一点就无法完成。而贪心（以及带记忆化的递归）在同样的输入上都只需要多项式时间。
用双指针 i（指向 s）、j（指向 p），并记下最近一个 * 的位置 star 和它当前匹配到的 s 的位置 mark。如果当前字符匹配（? 或相同），两个指针都前进；如果 p[j] 是 *，记下 star = j、mark = i，让 * 先匹配空串（只让 j 前进）；如果失配，而之前有 *，就让 * 多吃一个字符：mark 加一，i 回到 mark，j 回到 star + 1；如果失配又没有 *，返回失败。s 用完之后，p 剩下的必须全是 *。只需要记住最近的一个 *，因为之前的 * 已经可以匹配任何东西，回退到更早的 * 不会有更多收获。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(s, p): i = j = 0 star = -1 # 最近一个 * 在 p 里的位置 mark = 0 # 这个 * 当前"吃到"了 s 的哪个位置之前 while i < len(s): if j < len(p) and (p[j] == "?" or p[j] == s[i]): i += 1 j += 1 elif j < len(p) and p[j] == "*": star, mark = j, i # 先让 * 匹配空串，记下位置，以后失配时回来让它多吃一个字符 j += 1 elif star != -1: mark += 1 # 失配：回到最近的 *，让它多吃 s 的一个字符 i, j = mark, star + 1 else: return False while j < len(p) and p[j] == "*": # s 用完了，p 剩下的必须全是 * j += 1 return j == len(p)
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON ["aa","a"] → false ["aa","*"] → true ["cb","?a"] → false ["adceb","*a*b"] → true ["acdcb","a*c?b"] → false ["",""] → true
Java · 解法代码class Solution { public boolean isMatch(String s, String p) { int i = 0, j = 0; int star = -1; // 最近一个 * 在 p 里的位置 int mark = 0; // 这个 * 当前"吃到"了 s 的哪个位置之前 while (i < s.length()) { if (j < p.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) { i++; j++; } else if (j < p.length() && p.charAt(j) == '*') { star = j; mark = i; // 先让 * 匹配空串，记下位置 j++; } else if (star != -1) { mark++; // 失配：回到最近的 *，让它多吃 s 的一个字符 i = mark; j = star + 1; } else { return false; } } while (j < p.length() && p.charAt(j) == '*') j++; // s 用完了，p 剩下的必须全是 * return j == p.length(); } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl ["aa","a"] → false ["aa","*"] → true ["cb","?a"] → false ["adceb","*a*b"] → true ["acdcb","a*c?b"] → false ["",""] → true
Go · 解法代码func isMatch(s, p string) bool { i, j := 0, 0 star := -1 // 最近一个 * 在 p 里的位置 mark := 0 // 这个 * 当前"吃到"了 s 的哪个位置之前 for i < len(s) { if j < len(p) && (p[j] == '?' || p[j] == s[i]) { i++ j++ } else if j < len(p) && p[j] == '*' { star, mark = j, i // 先让 * 匹配空串，记下位置 j++ } else if star != -1 { mark++ // 失配：回到最近的 *，让它多吃 s 的一个字符 i, j = mark, star+1 } else { return false } } for j < len(p) && p[j] == '*' { // s 用完了，p 剩下的必须全是 * j++ } return j == len(p) }
$ go build -o bin . && ./bin < cases.jsonl ["aa","a"] → false ["aa","*"] → true ["cb","?a"] → false ["adceb","*a*b"] → true ["acdcb","a*c?b"] → false ["",""] → true
JavaScript · 解法代码function isMatch(s, p) { let i = 0, j = 0; let star = -1; // 最近一个 * 在 p 里的位置 let mark = 0; // 这个 * 当前"吃到"了 s 的哪个位置之前 while (i < s.length) { if (j < p.length && (p[j] === "?" || p[j] === s[i])) { i++; j++; } else if (j < p.length && p[j] === "*") { star = j; mark = i; // 先让 * 匹配空串，记下位置 j++; } else if (star !== -1) { mark++; // 失配：回到最近的 *，让它多吃 s 的一个字符 i = mark; j = star + 1; } else { return false; } } while (j < p.length && p[j] === "*") j++; // s 用完了，p 剩下的必须全是 * return j === p.length; }
$ node run.js < cases.jsonl ["aa","a"] → false ["aa","*"] → true ["cb","?a"] → false ["adceb","*a*b"] → true ["acdcb","a*c?b"] → false ["",""] → true
C++ · 解法代码#include <string> using namespace std; class Solution { public: bool isMatch(string s, string p) { int i = 0, j = 0; int star = -1; // 最近一个 * 在 p 里的位置 int mark = 0; // 这个 * 当前"吃到"了 s 的哪个位置之前 while (i < (int)s.size()) { if (j < (int)p.size() && (p[j] == '?' || p[j] == s[i])) { i++; j++; } else if (j < (int)p.size() && p[j] == '*') { star = j; mark = i; // 先让 * 匹配空串，记下位置 j++; } else if (star != -1) { mark++; // 失配：回到最近的 *，让它多吃 s 的一个字符 i = mark; j = star + 1; } else { return false; } } while (j < (int)p.size() && p[j] == '*') j++; // s 用完了，p 剩下的必须全是 * return j == (int)p.size(); } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl ["aa","a"] → false ["aa","*"] → true ["cb","?a"] → false ["adceb","*a*b"] → true ["acdcb","a*c?b"] → false ["",""] → true
共 18 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 18/18 Java 通过 18/18 Go 通过 18/18 JavaScript 通过 18/18 C++ 通过 18/18
贪心的最坏情形是：s 全是 a，模式是 * 加 n/2 个 a 再加一个 b：每次让 * 多吃一个字符，都要重新比较 n/2 个 a 才发现最后的 b 不匹配，所以总共是 O(n · n/2)。我用这个数据比较贪心和带记忆化的递归（也是平方），每个规模取三次中最快的一次：
s 的长度 n（s 全是 a，p = * + n/2 个 a + b，匹配不上） | 暴力解 | 本文解法
200 | 3.345 ms | 0.513 ms
400 | 20.319 ms | 2.155 ms
800 | 82.269 ms | 9.775 ms
1600 | 377.533 ms | 40.860 ms两者每翻一倍规模都增长约 4 到 6 倍，都是平方增长，与理论一致：贪心的平方最坏情形并没有比动态规划更好。贪心快约 6.5 到 9.4 倍，这个差别来自常数（不需要哈希表和递归调用），不是复杂度的差别。贪心的真正优势是空间：O(1)，而记忆化的递归需要 O(nm)。
Python 版本另外和记忆化递归做了随机对拍，s 由 a、b 组成，p 由 a、b、?、* 组成：
随机对拍 30000 组（s 取自 {a,b}、长 0 到 9，p 取自 {a,b,?,*}、长 0 到 7），solve 与 brute 的结果全部一致。另外四种语言只在上面 18 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 s = "adceb"、p = "*a*b"。* 先匹配空串，a 匹配成功，第二个 * 记下位置 (star = 2, mark = 1)；此后 b 与 d、c、e 都不匹配，每次失配就回到第二个 * 让它多吃一个字符，最后 b 匹配上 s 的最后一个字符。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。