Longest Common Subsequence · 數據結構與算法/leetcode/lintcode題解

# Longest Common Subsequence - tags: [[DP_Two_Sequence](# "一般有兩個數組或者兩個字符串，計算其匹配關系. 通常可用 `f[i][j]`表示第一個數組的前 i 位和第二個數組的前 j 位的關系。")] ### Source - lintcode: [(77) Longest Common Subsequence](http://www.lintcode.com/en/problem/longest-common-subsequence/) ~~~ Given two strings, find the longest common subsequence (LCS). Your code should return the length of LCS. Have you met this question in a real interview? Yes Example For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1. For "ABCD" and "EACB", the LCS is "AC", return 2. Clarification What's the definition of Longest Common Subsequence? https://en.wikipedia.org/wiki/Longest_common_subsequence_problem http://baike.baidu.com/view/2020307.htm ~~~ ### 題解求最長公共子序列的數目，注意這里的子序列可以不是連續序列，務必問清楚題意。求『最長』類的題目往往與動態規劃有點關系，這里是兩個字符串，故應為雙序列動態規劃。這道題的狀態很容易找，不妨先試試以`f[i][j]`表示字符串 A 的前 `i` 位和字符串 B 的前 `j` 位的最長公共子序列數目，那么接下來試試尋找其狀態轉移方程。從實際例子`ABCD`和`EDCA`出發，首先初始化`f`的長度為字符串長度加1，那么有`f[0][0] = 0`, `f[0][*] = 0`, `f[*][0] = 0`, 最后應該返回`f[lenA][lenB]`. 即 f 中索引與字符串索引對應(字符串索引從1開始算起)，那么在A 的第一個字符與 B 的第一個字符相等時，`f[1][1] = 1 + f[0][0]`, 否則`f[1][1] = max(f[0][1], f[1][0])`。推而廣之，也就意味著若`A[i] == B[j]`, 則分別去掉這兩個字符后，原 LCS 數目減一，那為什么一定是1而不是0或者2呢？因為不管公共子序列是以哪個字符結尾，在`A[i] == B[j]`時 LCS 最多只能增加1. 而在`A[i] != B[j]`時，由于`A[i]` 或者 `B[j]` 不可能同時出現在最終的 LCS 中，故這個問題可進一步縮小，`f[i][j] = max(f[i - 1][j], f[i][j - 1])`. 需要注意的是這種狀態轉移方程只依賴最終的 LCS 數目，而不依賴于公共子序列到底是以第幾個索引結束。 ### Python ~~~ class Solution: """ @param A, B: Two strings. @return: The length of longest common subsequence of A and B. """ def longestCommonSubsequence(self, A, B): if not A or not B: return 0 lenA, lenB = len(A), len(B) lcs = [[0 for i in xrange(1 + lenA)] for j in xrange(1 + lenB)] for i in xrange(1, 1 + lenA): for j in xrange(1, 1 + lenB): if A[i - 1] == B[j - 1]: lcs[i][j] = 1 + lcs[i - 1][j - 1] else: lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]) return lcs[lenA][lenB] ~~~ ### C++ ~~~ class Solution { public: /** * @param A, B: Two strings. * @return: The length of longest common subsequence of A and B. */ int longestCommonSubsequence(string A, string B) { if (A.empty()) return 0; if (B.empty()) return 0; int lenA = A.size(); int lenB = B.size(); vector<vector<int> > lcs = \ vector<vector<int> >(1 + lenA, vector<int>(1 + lenB)); for (int i = 1; i < 1 + lenA; i++) { for (int j = 1; j < 1 + lenB; j++) { if (A[i - 1] == B[j - 1]) { lcs[i][j] = 1 + lcs[i - 1][j - 1]; } else { lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]); } } } return lcs[lenA][lenB]; } }; ~~~ ### Java ~~~ public class Solution { /** * @param A, B: Two strings. * @return: The length of longest common subsequence of A and B. */ public int longestCommonSubsequence(String A, String B) { if (A == null || A.length() == 0) return 0; if (B == null || B.length() == 0) return 0; int lenA = A.length(); int lenB = B.length(); int[][] lcs = new int[1 + lenA][1 + lenB]; for (int i = 1; i < 1 + lenA; i++) { for (int j = 1; j < 1 + lenB; j++) { if (A.charAt(i - 1) == B.charAt(j - 1)) { lcs[i][j] = 1 + lcs[i - 1][j - 1]; } else { lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]); } } } return lcs[lenA][lenB]; } } ~~~ ### 源碼分析注意 Python 中的多維數組初始化方式，不可簡單使用`[[0] * len(A)] * len(B)]`, 具體原因是因為 Python 中的對象引用方式 [Stackoverflow](#)。 ### 復雜度分析兩重for 循環，時間復雜度為 O(lenA×lenB)O(lenA \times lenB)O(lenA×lenB), 使用了二維數組，空間復雜度也為 O(lenA×lenB)O(lenA \times lenB)O(lenA×lenB). ### Reference - Stackoverflow > . [Python multi-dimensional array initialization without a loop - Stack Overflow](http://stackoverflow.com/questions/3662475/python-multi-dimensional-array-initialization-without-a-loop)[ ?](# "Jump back to footnote [Stackoverflow] in the text.")