java - 在寻找最长公共(public)子串 [DP] 时如何获得空间复杂度 O(n)？

Question

¡你好!

我正在尝试使用动态规划来找到具有良好时间和空间复杂度的两个字符串之间的最长公共(public)子字符串。我可以找到一个具有 O(n^2) 时间和空间复杂度的解决方案:

public static String LCS(String s1, String s2){
    int maxlen = 0;            // stores the max length of LCS      
    int m = s1.length();
    int n = s2.length();
    int endingIndex = m;  // stores the ending index of LCS in X

    // lookup[i][j] stores the length of LCS of substring
    // X[0..i-1], Y[0..j-1]
    int[][] lookup = new int[m + 1][n + 1];

    // fill the lookup table in bottom-up manner
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            // if current character of X and Y matches
            if (s1.charAt(i - 1) == s2.charAt(j - 1))
            {
                lookup[i][j] = lookup[i - 1][j - 1] + 1;

                // update the maximum length and ending index
                if (lookup[i][j] > maxlen)
                {
                    maxlen = lookup[i][j];
                    endingIndex = i;
                }
            }
        }
    }

    // return Longest common substring having length maxlen
    return s1.substring(endingIndex - maxlen, endingIndex);

}

我的问题是:如何获得更好的空间复杂度？

提前致谢!

Answer 1

使用动态规划查找两个字符串的 LCS 的最佳时间复杂度是 O(n^2)。我试图找到解决该问题的另一种算法，因为这是我的大学项目之一。但我能找到的最好的东西是复杂度为 O(n^3) 的算法。这个问题的主要解决方案是使用“递归关系”，它占用的空间更少，但过程却更多。但就像“斐波那契数列”一样，计算机科学家使用动态规划来降低时间复杂度。递归关系代码:

void calculateLCS(string &lcs , char frstInp[] , char secInp[] , int lengthFrstInp ,  int lengthSecInp) {

if (lengthFrstInp == -1 || lengthSecInp == -1)
    return;

if (frstInp[lengthFrstInp] == secInp[lengthSecInp]) {
    lcs += frstInp[lengthFrstInp];
    lengthFrstInp--;
    lengthSecInp--;
    calculateLCS(lcs, frstInp, secInp, lengthFrstInp, lengthSecInp);

}


else {

    string lcs1 ="";
    string lcs2 ="";    
    lcs1 = lcs;
    lcs2 = lcs;
    calculateLCS(lcs1, frstInp, secInp, lengthFrstInp, lengthSecInp - 1);
    calculateLCS(lcs2, frstInp, secInp, lengthFrstInp - 1, lengthSecInp);

    if (lcs1.size() >= lcs2.size())
        lcs = lcs1;
    else
        lcs = lcs2;

}