动态规划——最长公共子串：理解space优化

Question

我正在解决一个非常典型的问题，即两个字符串的最长公共子串。问题陈述很清楚：对于两个字符串 s1 和 s2，求它们的最长公共子串的长度。 dp数组表示的状态的定义我能看懂。它是一个二维数组，其中二维仅表示每个字符串中字符的索引（但仅基于 1 而不是基于 0）。原始解决方案代码如下所示，对我来说很清楚：

  public int findLCSLength(String s1, String s2) {
    int[][] dp = new int[s1.length()+1][s2.length()+1];
    int maxLength = 0;
    for(int i=1; i <= s1.length(); i++) {
      for(int j=1; j <= s2.length(); j++) {
        if(s1.charAt(i-1) == s2.charAt(j-1)) {
          dp[i][j] = 1 + dp[i-1][j-1];
          maxLength = Math.max(maxLength, dp[i][j]);
        }
      }
    }
    return maxLength;
  }

这个解决方案显然可以优化，因为 dp[i][j] 的状态仅取决于前一行，这意味着两行对于 dp 数组就足够了。所以我把dp数组做了一个二维数组，用mod操作映射2.

范围内的索引

  static int findLCSLength(String s1, String s2) {
    int[][] dp = new int[2][s2.length()+1];
    int maxLength = 0;
    for(int i=1; i <= s1.length(); i++) {
      for(int j=1; j <= s2.length(); j++) {
        if(s1.charAt(i-1) == s2.charAt(j-1)) {
          dp[i%2][j] = 1 + dp[(i-1)%2][j-1];
          maxLength = Math.max(maxLength, dp[i%2][j]);
        }
      }
    }
    return maxLength;
  }

但是我的代码没有为所有测试用例生成正确答案。我找到了一个代码片段，它给出了所有测试用例的正确答案，但只有一个额外的操作，因为我错过了。

  static int findLCSLength(String s1, String s2) {
    int[][] dp = new int[2][s2.length()+1];
    int maxLength = 0;
    for(int i=1; i <= s1.length(); i++) {
      for(int j=1; j <= s2.length(); j++) {

        //This is the only extra line I missed
        dp[i%2][j] = 0;

        if(s1.charAt(i-1) == s2.charAt(j-1)) {
          dp[i%2][j] = 1 + dp[(i-1)%2][j-1];
          maxLength = Math.max(maxLength, dp[i%2][j]);
        }
      }
    }
    return maxLength;
  }

我的代码失败的情况之一是“passport”和“ppsspt”，我的代码产生了 4，但正确答案显然是 3。我很困惑，但是这条线，这条线是做什么的，为什么有必要？希望任何人都可以提供帮助。

Answer 1

它重置当前计数。

您的代码在以下情况下设置此变量：

if(s1.charAt(i-1) == s2.charAt(j-1)) {

但没有其他方法可以将其设置为 0，这实际上就是该代码的作用。

所以考虑一下：

s1.charAt(i-1) != s2.charAt(j-1)

您在此数组位置中的先前值将在不应该的情况下转移到下一个 sub-string 比较。

动态规划——最长公共子串：理解space优化

Dynamic programming--Longest Common Substring: Understanding the space optimization

algorithm

dynamic-programming