从朴素递归到 FreeBSD 源码：通配符匹配的

在文件管理器搜 *.cpp，或者在数据库里写 LIKE '%bug%'——这俩背后都是同一个问题：带通配符的字符串匹配。

规则就两条：? 匹配一个任意字符，* 能匹配任意长度，包括空串。比如 a*d 能收下 ad、abcd。问题是，给定任意文本和模式，怎么判断它俩能不能对上？这可是 LeetCode 上的 hard 第 44 题，不少老手都得栽。

最自然的解法是递归。但朴素递归有个致命伤：重复计算。拿 2k 个 a 去匹配 k 组 a* 加一个永远等不来的 b，k 每加 2，调用次数膨胀约 15 倍。病根就在这儿，得靠一张 memo 表把复杂度拉回 O(mn)。

其实还有更绝的贪心回溯法。核心思路是给 ` 留一颗“后悔药”：让它先少吃点，一路往后匹配；一旦撞墙，就回来让 ` 多吃一个字符。而且我们只需要记住最后一颗后悔药，因为更早的星号根本不用管。FreeBSD 从 1989 年起用的就是这套算法，沿用至今。

下次敲下 *.cpp 的时候，想想这半秒钟背后的贪心与回溯。