首页 > 代码库 > Lintcode:Longest Common Subsequence 解题报告

Lintcode:Longest Common Subsequence 解题报告

Longest Common Subsequence

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

Your code should return the length of LCS.

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

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

说明
What‘s the definition of Longest Common Subsequence?

* The longest common subsequence (LCS) problem is to find the longest subsequence common to all sequences in a set of sequences (often just two). (Note that a subsequence is different from a substring, for the terms of the former need not be consecutive terms of the original sequence.) It is a classic computer science problem, the basis of file comparison programs such as diff, and has applications in bioinformatics.

* https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

标签 Expand

 

SOLUTION 1:

DP. 

1. D[i][j] 定义为s1, s2的前i,j个字符串的最长common subsequence. 

2. D[i][j] 当char i == char j, D[i - 1][j - 1] + 1

    当char i != char j, D[i ][j - 1], D[i - 1][j] 里取一个大的(因为最后一个不相同,所以有可能s1的最后一个字符会出现在s2的前部分里,反之亦然。

技术分享
 1 public class Solution { 2     /** 3      * @param A, B: Two strings. 4      * @return: The length of longest common subsequence of A and B. 5      */ 6     public int longestCommonSubsequence(String A, String B) { 7         // write your code here 8         if (A == null || B == null) { 9             return 0;10         }11         12         int lenA = A.length();13         int lenB = B.length();14         int[][] D = new int[lenA + 1][lenB + 1];15         16         for (int i = 0; i <= lenA; i++) {17             for (int j = 0; j <= lenB; j++) {18                 if (i == 0 || j == 0) {19                     D[i][j] = 0;20                 } else {21                     if (A.charAt(i - 1) == B.charAt(j - 1)) {22                         D[i][j] = D[i - 1][j - 1] + 1;23                     } else {24                         D[i][j] = Math.max(D[i - 1][j], D[i][j - 1]);25                     }26                 }27             }28         }29         30         return D[lenA][lenB];31     }32 }
View Code

 

 https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/lintcode/dp/longestCommonSubsequence.java

 

Lintcode:Longest Common Subsequence 解题报告