lintcode:最长公共子序列

题目

最长公共子序列

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

样例

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

给出 "ABCD" 和 "EACB"，这个LCS是"AC"返回 2

注意

说明

最长公共子序列的定义：

最长公共子序列问题是在一组序列（通常2个）中找到最长公共子序列（注意：不同于子串，LCS不需要是连续的子串）。该问题是典型的计算机科学问题，是文件差异比较程序的基础，在生物信息学中也有所应用。
https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

解题

最长上升子序列求的都是最长，应该动态规划求解.画图下面的图，1 的位置就是相同的元素。从（0,1）开始是第一个相同的元素A，后面的设为（i,j）要想是后续连续的公共子序列则，i>0 j>1 也就是说，后面点的横纵坐标一定要大于前面点的横纵坐标。

	E	A	C	B
A		1
B				1
C			1
D

这样可以定义一个很大的数组，如何根据数组中1出现的位置找到最长的子序列，设这个数组是Arr

Arr[i][j] =1 表示元素相同，如何找出下一个点的横坐标大于i 纵坐标大于j的，并且一直找下去。。。下面不知道怎么办了。。。

维基百科说得很好

设两个字符串是A、B ，其长度是lenA、lenB 定义数组Arr[lenA+1][lenB+1] ,Arr[i][j] 表示A[0--i] ,B[0--j] 两个字符串的最长公共子序列长度,对下面的一个位置 i+ 1 、j+ 1

1.若A[i+1] == B[j+1], 则Arr[i+1][j+1] = Arr[i][j] + 1

2.若A[i+1]!=B[j+1],Arr[i+1][j+1] 应该是根据其前面一个元素的值确定的，这里是个矩阵其前面的元素是Arr[i][j],Arr[i+1][j],Arr[i][j+1]

Arr[i][j]表示A[0--i] ,B[0--j] 两个字符串的最长公共子序列长度

Arr[i+1][j]表示A[0--i+1] ,B[0--j] 两个字符串的最长公共子序列长度

Arr[i][j+1]表示A[0--i] ,B[0--j+1] 两个字符串的最长公共子序列长度

A[i+1]!=B[j+1], 可能A[i+1]==B[j] A[i]==B[j+1] 这里是交叉相等的情况所以Arr[i+1][j+1] =max（Arr[i+1][j],Arr[i][j+1]）

同时要注意：数组Arr长度是lenA+1 lenB+1 第一行第一列的元素都是0 这样在求解的时候比较方便

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) {
        // write your code here
        int lenA = A.length();
        int lenB = B.length();
        if(A== null || B == null||lenA == 0|| lenB ==0)
            return 0;
        int d[][] = new int[lenA + 1][lenB + 1];
        for(int i=1;i<= lenA;i++){
            for(int j=1;j<=lenB;j++){
                // if(i==0)
                    // d[i][j] = 0;
                // if(j==0)
                    // d[i][j] = 0;
                char a = A.charAt(i-1);
                char b = B.charAt(j-1);
                if(a ==b ){
                    d[i][j] = d[i-1][j-1] + 1;
                }else{
                    d[i][j] = Math.max(d[i-1][j],d[i][j-1]);
                }
            }
        }
        return d[lenA][lenB];
    }
}

Java Code

Python

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

递归求解超时

    public int longestCommonSubsequence(String A, String B) {
        // write your code here
        int lenA = A.length();
        int lenB = B.length();
        if(A== null || B == null||lenA == 0|| lenB ==0)
            return 0;
        char a = A.charAt(0);
        char b = B.charAt(0);
        if( a == b){
            String subA = A.substring(1);
            String subB = B.substring(1);
            return 1 + longestCommonSubsequence(subA,subB);
        }else{
            String subA = A.substring(1);
            String subB = B.substring(1);
            int lcs1  = longestCommonSubsequence(A,subB);
            int lcs2  = longestCommonSubsequence(subA,B);
            return Math.max(lcs1,lcs2);
        }
        
    }