Longest Common Subsequence

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

Your code should return the length of LCS.

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

Example

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

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

Solution

单序列型研究如何切，双序列型研究最后一个数字或者字母。

双序列型动态规划

图加上故事，非常有助于记忆。

abcd = abcd then f[i - 1][j - 1] + 1

state: f[i][j]代表了第一个sequence的前i个数字/字符，配上第二个sequence的前j个... function: f[i][j] =研究第i个和第j个的匹配关系 initialize: f[i][0]和f[0][i]

answer: f[s1.length()][s2.length()]

state: f[i][j]表示前i个字符配上前j个字符的LCS的长度 function: f[i][j] = MAX(f[i-1][j], f[i][j-1], f[i-1][j-1] + 1) // a[i] == b[j]

= MAX(f[i-1][j], f[i][j-1]) // a[i] != b[j] intialize: f[i][0] = 0 f[0][j] = 0

answer: f[a.length()][b.length()]

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 len(A) == 0 or len(B) == 0:
            return 0
        # write your code here
        m = len(A) 
        n = len(B)

        f = [[0 for x in range(n + 1)] for y in range(m + 1)]

        f[0][0] = 0

        for i in range(1,m + 1):
            for j in range(1,n + 1):
                if A[i - 1] == B[j - 1]:
                    f[i][j] = f[i - 1][j - 1] + 1
                else:
                    f[i][j] = max(f[i-1][j],f[i][j-1])
        return f[m][n]