java - LeetCode正则表达式问题中重叠子问题的可视化以及DP的使用

Question

我刚刚解决了this leetcode.com 上的问题(10. 正则表达式匹配)使用递归。我能够理解递归解决方案。然而，当我看到这段代码的优化版本时，建议我应该使用动态规划。我不明白为什么我们需要动态编程？

• 我认为这个问题没有重叠的子问题。为什么我们应该使用内存或制表？我无法想象重叠的子问题。

• 这是我到目前为止所达到的目标。这是我的解决方案:

   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));
  }
  

我对递归解决方案的理解是，我可以查看模式中的下一个字符是否是 *，那么可能有两种情况:

1. 我们跳过当前字符以及下一个字符(*)，并从索引 2 中获取模式的子字符串，并将模式的剩余子字符串与当前文本进行匹配。这说明 * 前面的字符出现了“0”次。
2. 模式中的 * 会不断吸收文本中的匹配字符。只要我们不断获得相同的角色，他们就会不断匹配星星，我们就会继续前进。

另一种情况是，如果下一个字符不是“*”，那么我们检查当前字符是否匹配，如果匹配，则检查两个字符的剩余子字符串。

我尝试使用以下命令进行空运行:

Input: s = "mississippi" p = "mis*is*p*." Output: false

我可以先想象一下 m 和 m 匹配， 我和我匹配 (到目前为止是线性递归)。 现在开始复杂的部分，因为 s 和 s 匹配，但 s 的下一个字符是星号。如果我调用，匹配“0”出现作为场景 1，并吸收 * 中的匹配字符作为场景 2，那么递归调用将如下所示:

Scenario 1 : text is ssissippi and remaining pattern is isp.

s and i characters didn't match

Scenario 2 : remaining text is sissippi and pattern is sisp*.

Scenario 1 : text is sissippi and remaining pattern is isp.

s and i characters didn't match

Scenario 2 : remaining text is issippi and pattern is sisp*.

Scenario 1 : text is issippi and remaining pattern is isp.

characters matched so next recursive call with text : ssippi and pattern as : sp.

Scenario 1 : text is ssippi and remaining pattern is p*.

Scenario 1 : text is ssippi and remaining pattern is .

characters matched so next recursive call with text : sippi and pattern as :

Scenario 2 : remaining text is sippi and pattern is p*.

Scenario 2 : remaining text is sippi and pattern is sp.

Scenario 1 : text is sippi and remaining pattern is p*.

Scenario 1 : text is sippi and remaining pattern is .

characters matched so next recursive call with text : ippi and pattern as : Scenario 2 : remaining text is ippi and pattern is p*.

Scenario 2 : remaining text is ippi and pattern is sp.

Scenario 1 : text is ippi and remaining pattern is p*.

Scenario 1 : text is ippi and remaining pattern is .

characters matched so next recursive call with text : ppi and pattern as :

Scenario 2 : remaining text is ppi and pattern is p*.

Scenario 2 : remaining text is ppi and pattern is sp.

Scenario 2 : remaining text is ssippi and pattern is sisp*.

最后返回False。

在这个解决方案中，我无法弄清楚是否存在任何重叠的子问题或我们可以重复使用的任何解决方案？

我什至尝试在 YouTube 上查找。 This guy没有告诉我们如何达到这个解决方案，他只是简单地运行该解决方案，因为他知道这是一个 DP 问题。

我们如何判断这是否是 DP 问题？针对这个问题达成 DP 解决方案背后的直觉是什么？

我在互联网上查了很多资料，但仍然无法弄清楚重叠的子问题在哪里，以及我们如何断定它是否是 DP 问题。我也尝试为此创建一棵递归树，但仍然无法弄清楚我们可以在哪里重复使用之前计算的解决方案。

任何人都可以帮助我可视化重叠的子问题，并帮助我总结如何确定它是否是 DP 问题并找到自下而上的解决方案？

Answer 1

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

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

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

发生这种情况是因为，文本的“hh”可以通过两种方式使用。模式的 "h" 可以与文本的第一个和第二个 "h" 匹配。但无论哪种方式，匹配 "hh" 都会从模式中占用 ".*h" ，并且剩下 "T" 和 “.*P”。

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