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

Question

你好！

我正在尝试寻找两个字符串之间最长的公共子字符串，并使用动态编程，具有良好的时间和空间复杂性。我可以找到一个时间和空间复杂度为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;

}