乐趣区

关于算法-数据结构:最长公共子序列LCS

jiezi

最近刚好算法试验做了这个, 水一篇博客吧

算法思路

根本剖析:

假如字符串 A 的长度为 m, 字符串 B 的长度为 n, 应用一个数组 fm 示意对应后果, 其中 f[i][j] 示意 A.substr(0, i) 和 B.substr(0, j)这两个子字符串的LCS.

思考 f[i][j], 他总是能够从上方⬆ (即不应用 A 的第 i 个字符) 和 左方⬅(不应用 B 的第 j 个字符)两个方向转移过去, 因而有f[i][j] = max(f[i – 1][j], f[i][j – 1]);

此外, 如果A[i] == B[j], 那么它能够从左上方转移过去, 此时有f[i][j] = max(f[i][j], f[i – 1][j – 1] + 1);

空间优化:

上述剖析曾经能够残缺地解决 LCS 问题, 想求出 LCS 只须要在转移的时候进行记录就行, 不过空间复杂度是 O(mn) 的, 而后通过咱们的剖析过程能够看到, 转移的时候只波及了以后行和上一行(这里假如行 size 更小, 如果列 size 更小的话同理).

因而咱们能够用两个长度为 m + 1 的数组, 通过不停更新来实现这个算法.

空间进一步优化:

通过上一步优化之后所用空间为两个长度为 m + 1的数组, 以及常数个额定变量. 不过还能够更进一步优化, 因为从头至尾咱们转移到 [i][j] 的时候只和三个地位的值无关: 正上方 [i – 1][j], 左方[i][j – 1] 和左上方[i – 1][j – 1].

因而咱们能够思考用一个数组来示意, 在只应用一个数组的状况下, 更新前 f[j] 就是上一轮更新后的上方 f[i – 1][j], 而f[j – 1] 也就是左方 f[i][j – 1], 也就是说咱们在更新f[j] 的时候, 须要的三个值中的两个都在这个数组中了, 那么咱们只须要缓存 f[i – 1][j – 1] 就行了. 这种状况下, 空间为一个长度为 m + 1 的数组, 加上两个额定变量. 空间复杂度较低.

代码

奢侈:

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {int n1 = text1.size(), n2 = text2.size();
        vector<vector<int>> dp(n1 + 1, vector<int> (n2 + 1, 0));
        for (int i = 1; i <= n1; ++i) {for (int j = 1; j <= n2; ++j) {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // 从正上方和左方转移
                if (text1[i - 1] == text2[j - 1]) {dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1); // 从斜上方转移
                }
            }
        }
        return dp[n1][n2];
    }
};

两个数组:

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {int n1 = text1.size(), n2 = text2.size();
        int minlen = min(n1, n2), maxlen =max(n1, n2); // 应用较小的长度作为数组长度
        vector<int> pre(minlen + 1, 0);
        vector<int> cur(minlen + 1, 0);
        for (int i = 1; i <= maxlen; ++i) {for (int j = 1; j <= minlen; ++j) {cur[j] = max(cur[j - 1], pre[j]); // 从上方和左方转移
                // 从左上方转移
                if (n1 > n2 && text1[i - 1] == text2[j - 1]) {cur[j] = max(cur[j], pre[j - 1] + 1);
                } 
                if (n1 <= n2 && text2[i - 1] == text1[j - 1]) {cur[j] = max(cur[j], pre[j - 1] + 1);
                }
            }
            // 更新 pre
            for (int j = 1; j <= minlen; ++j) {pre[j] = cur[j];
            }
        }
        return cur[minlen];
    }
};

一个数组:

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {int n1 = text1.size(), n2 = text2.size();
        int minlen = min(n1, n2), maxlen = max(n1, n2);
        vector<int> cur(minlen + 1, 0); // 应用一个数组实现
        for (int i = 1; i <= maxlen; ++i) {
            int pre = 0;
            for (int j = 1; j <= minlen; ++j) {int nextPre = cur[j];
                cur[j] = max(cur[j - 1], cur[j]);  // 从上方和左方转移, 自身就是上方
                // 从左上方转移
                if (n1 > n2 && text1[i - 1] == text2[j - 1]) {cur[j] = max(cur[j], pre + 1);
                } 
                if (n1 <= n2 && text2[i - 1] == text1[j - 1]) {cur[j] = max(cur[j], pre + 1);
                }
                // 更新 f[i - 1][j - 1]
                pre = nextPre;
            }
        }
        return cur[minlen];
    }
};
退出移动版