python - 实现模式匹配 - 何时使用缓存？

Question

任务是为整个字符串实现一个简单的模式匹配，其中模式可能包括 .和 * .
以下code创建一个 DFS，同时为文本和模式维护两个指针。它还利用缓存来实现不重复工作的明显原因。
我试图测试 isMatch有几个输入，但我没有看到缓存被使用过(“来自缓存”行从未被调用)。你能帮我展示一个使用缓存的例子吗？
谢谢

def isMatch(s, p):
    cache = {}

    def dfs(i, j):
        print(f"dfs was called with i={i}, j={j}")
        if (i, j) in cache:
            print((i, j), "from cache")
            return cache[(i, j)]
        
        if i >= len(s) and j >= len(p):
            return True
        if j >= len(p):
            return False

        match = i < len(s) and (s[i] == p[j] or p[j] == ".")
        if (j + 1) < len(p) and p[j+1] == "*":
            cache[(i, j)] = dfs(i, j+2) or (match and dfs(i + 1, j))
            return cache[(i, j)]

        if match:
            cache[(i, j)] = dfs(i + 1, j + 1)
            return cache[(i, j)]

        cache[(i, j)] = False
        return False

    return dfs(0, 0)


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

Answer 1

编辑:缓存在这种情况下很有用 "ab", "a*a*"
状况 :

人物a可以同时匹配第一个和第二个子表达式。

整体无匹配

节点 (1,2) 可以从两条路径到达

探索的第一条路径 = 跳过第一个子表达式 (0, 0) -> (0, 2) -> (1, 2)

探索的第二条路径 = 匹配第一个子表达式 (0, 0) -> (1, 0) -> (1, 2)

这里的问题是 dfs(i, j+2)当 s[i] 和 p[j+2] 匹配时为假。
dfs(i, j+2) 将触发 dfs(i, j+4), dfs(i, j+6), ..., dfs(i, j+2k)
dfs(i, j+4) 将触发 dfs(i, j+6), ...., dfs(i, j+2k)
...
dfs(i, j+2k-2) 会触发dfs(i, j+2k)
您只需要缓存 dfs(i, j+2)

v = dfs(i, j+2)
cache[(i, j+2)] = v
return v or (match and dfs(i + 1, j))

错误答案:永远不会读取此缓存，无论 s 和 p
要获得缓存命中，您需要一个给定的元组 (x, y)，其中包含从 (0, 0) 到 (x, y) 的多条路径。要从多条路径到达 (x, y)，需要有一个分支。
那么我们什么时候分支？唯一的地方是cache[(i, j)] = dfs(i, j+2) or (match and dfs(i + 1, j))

当正则表达式最终匹配​​到重复模式时，如 a*

dfs(i, j+2)为假(如果为真， the whole expression is already true, and due to short circuit execution, the right part of the or is never run )

匹配为真:再次，由于短路，如果没有匹配，则不执行正确的部分

dfs(i+1, j)也是假的。 (x, y)不能既真又假。

所以缓存理论上是在 s 时命中的不匹配 p .
仅当我们用完 0 个或多个表达式(如 a*)时，我们才存储错误匹配。并且两个数字不匹配(例如 isMatch('a', 'b') )。此时，算法无论如何都需要停止，因此没有理由缓存任何内容。
当这种情况发生时，我们在这里:

        cache[(i, j)] = False
        return False

此时，没有更多的分支。即只有一种方法可以到达那里。所以缓存永远不会被读取。