首页 > 代码库 > 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 }
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/lintcode/dp/longestCommonSubsequence.java
Lintcode:Longest Common Subsequence 解题报告