可视化LeetCode正则表达式问题中的重叠子问题和DP的使用

Question

我刚刚在 leetcode.com 上使用递归解决了这个问题（10.正则表达式匹配）。我能够理解递归解决方案。但是，当我看到这段代码的优化版本时，建议我应该使用Dynamic Programming。我不明白为什么我们需要动态编程？我没有看到这个问题有重叠的子问题。我们为什么要使用记忆或制表？我无法想象重叠的子问题。这是我到目前为止到达的地方。这是我的解决方案：public static boolean isMatch(String text, String pattern) {if (pattern.isEmpty())    return text.isEmpty();boolean first_match = (!text.isEmpty() && (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));if (pattern.length() >= 2 && pattern.charAt(1) == '*') {    return isMatch(text, pattern.substring(2))|| first_match && isMatch(text.substring(1), pattern);} else {    return first_match && isMatch(text.substring(1), pattern.substring(1));}我对递归解决方案的理解是，我可以看到模式中的下一个字符是否是 *，那么可能有两种情况：我们跳过当前字符和下一个字符（*）并从索引 2 中获取模式的子字符串，并将模式的剩余子字符串与当前文本进行匹配。这说明 * 前的字符出现“0”次。模式中的 * 将不断吸收文本中的匹配字符。只要我们继续获得相同的角色，他们就会继续匹配明星，我们就会继续前进。另一种情况是，如果下一个字符不是“*”，那么我们检查当前字符是否匹配，如果是，则检查两者的剩余子字符串。我尝试使用以下方法进行干运行：输入：s = "mississippi" p = "mis*is*p*." 输出：假我可以想象第一个 m 和 m 匹配，i 和 i 匹配（到目前为止是线性递归）。现在开始复杂的部分，因为 s 和 s 匹配但 s 的下一个字符是星号。如果我调用，匹配 '0' 出现作为场景 1 并吸收 * 作为场景 2 中的匹配字符，那么递归调用将如下所示：场景 1： text 是 ssissippi ，剩余模式是p。s 和 i 字符不匹配场景 2：剩余文本是 sissippi，模式是 s是p*。场景 1：文本是 sissippi，剩余模式是p。s 和 i 字符不匹配场景 2：剩余文本是 issippi，模式是 s是p*。场景 1： text 是 issippi ，剩余模式是p。字符匹配所以下一个递归调用文本：ssippi 和模式为：s p。场景 1：文本为 ssippi，剩余模式为 p*。场景 1：文本为 ssippi，剩余模式为 .字符匹配所以下一个递归调用文本：sippi 和模式为：场景 2：剩余文本为 sippi，模式为 p*。场景 2：剩余文本为 sippi ，模式为 s p。场景 1：文本是 sippi，剩余模式是 p*。场景 1：文本是 sippi，剩余模式是 .字符匹配，因此下一个递归调用与文本：ippi 和模式为：场景 2：剩余文本为 ippi，模式为 p*。场景2：剩余文本为 ippi ，模式为 s p。场景 1：文本为 ippi，剩余模式为 p*。场景1：文本为ippi，剩余模式为.字符匹配所以下一个递归调用文本：ppi 和模式为：场景 2：剩余文本为 ppi，模式为 p*。场景2：剩余文本为 ppi ，模式为 s p。场景 2：剩余文本是 ssippi，模式是 s是p*。最后返回False。在此解决方案中，我无法确定是否存在任何重叠的子问题或任何我们可以重用的解决方案？我什至尝试在youtube上查找。这家伙没有告诉我们是如何得到这个解决方案的，他只是简单地试运行这个解决方案，因为他知道这是一个 DP 问题。我们如何确定这是否是 DP 问题？为这个问题达成 DP 解决方案背后的直觉是什么？我在互联网上查了很多资料，但我仍然无法弄清楚重叠的子问题在哪里，以及我们如何得出结论是否是 DP 问题。我也尝试为这个树制作一个递归树，但仍然无法弄清楚我们可以在哪里重新使用以前计算的解决方案。任何人都可以帮助我想象重叠的子问题，并帮助我得出结论，您如何确定它是否是 DP 问题并找到自下而上的解决方案？

Answer 1

这是一个测试用例， text = "hhT"， pattern = ".*h.*P"。

尝试在isMatch函数调用的第一行打印文本和模式。您会看到文本"T"和图案".*P"出现两次。所以是的，这个问题确实有重叠的子问题。

我努力想出一个例子的部分原因是你的代码非常优雅。我写得比较糟糕的代码有更多的重叠。

之所以发生这种情况，"hh"是因为可以通过两种方式使用文本。该"h"图案可以被匹配到第一和第二"h"文本的。但无论哪种方式，匹配"hh"都会".*h"从模式中获取，而你只剩下"T"and ".*P"。

因此，与斐波那契或其他经典 DP 问题不同，这里的子问题重叠并不能保证发生。但它可能会发生，特别是当您有很多特殊字符时。