Longest Common Subsequence

Question

Given two strings, find the longest common subsequence (LCS).

Your code should return the length of LCS.

Example For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.

For "ABCD" and "EACB", the LCS is "AC", return 2.

Thoughts

其他的与longest common substring相同，connection function不一样

如果A[i-1] == B[j-1]，lcs的长度就是前面dp[i-1][j-1]加一个 如果A[i-1] != B[j-1], 这个char就不能在lcs里，就要在前面的结果中找已有的最大结果

connection function:
    if A[i-1] == B[j-1]:
        dp[i][j] = dp[i-1][j-1] + 1
    else:
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Solution

class Solution:
    """
    @param A, B: Two strings.
    @return: The length of longest common subsequence of A and B.
    """
    def longestCommonSubsequence(self, A, B):
        # write your code here
        if not A or not B:       
            return 0  
        maxNum = 0
        dp = [[0 for j in range(len(B)+1)] for i in range(len(A)+1)]
        for i in range(1, len(A)+1):  
            for j in range(1, len(B)+1):                         
                    if A[i-1] == B[j-1]:                        
                        dp[i][j] = dp[i-1][j-1] + 1   
                        if dp[i][j] > maxNum:
                            maxNum = dp[i][j]
                    else:        
                        dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 
                        if dp[i][j] > maxNum:
                            maxNum = dp[i][j]
        return maxNum