实现含.和*的模式匹配：DFS代码缓存未触发，求可触发的测试用例

可触发缓存的测试用例 #

你之前使用的测试用例不会触发缓存，是因为其递归路径中每个(i,j)坐标对只会被访问一次，没有重复查询的场景。要触发缓存命中，只需构造存在重叠递归路径的输入，示例如下：

示例1：重叠a*匹配场景

res = isMatch("aaab", "a*a*b")
print(res)

运行后你会看到多条from cache日志打印。

示例2：.*组合匹配场景

res = isMatch("aaaaa", ".*.*a")
print(res)

这个测试用例也会频繁触发缓存查询。

触发原理

当模式串中存在多个可匹配任意长度字符的*通配符组合时，不同的匹配决策（跳过当前*直接匹配后续规则，或用当前*多匹配一个字符再继续）最终会落到同一个(i,j)坐标对，此时已缓存的计算结果就会被直接调用。

内容的提问来源于stack exchange，提问作者Elimination