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

我对递归解决方案的理解是，如果模式中的下一个字符是 *，那么可能有 2 种情况:

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" 文本可以通过两种方式使用。 pattern 的 "h" 可以匹配文本的第一个和第二个 "h"。但无论哪种方式，匹配 "hh" 都会占用模式中的 ".*h"，而你只剩下 "T" 和 ".*P".

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