LintCode 77 [Longest Common Subsequence]

原题

给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。

给出"ABCD" 和 "EDCA"，这个LCS是 "A" (或 D或C)，返回1
给出** "ABCD"** 和 "EACB"，这个LCS是"AC"返回 2

解题思路

• 双序列型动态规划 - Two Sequence DP
• cache[i][j]表示第一个字符串的前i个字符和第二个字符串的前j个字符的最长公共子序列的长度
• 状态转移方程：
• 如果str1[i] != str2[j]
  cache[i][j] = max(cache[i][j - 1], cache[i - 1][j])
• 如果str1[i] != str2[j]
  cache[i - 1][j - 1] + 1

完整代码

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
            
        cache = [[0 for i in range(len(A) + 1)] for j in range(len(B) + 1)]
        
        for i in range(1, len(B) + 1):
            for j in range(1, len(A) + 1):
                if A[j - 1] == B[i - 1]:
                    cache[i][j] = cache[i - 1][j - 1] + 1
                else:
                    cache[i][j] = max(cache[i][j - 1], cache[i - 1][j])
        
        return cache[len(B)][len(A)]