Lintcode: Longest Common Subsequence

Given two strings, find the longest comment subsequence (LCS).Your code should return the length of LCS.ExampleFor "ABCD" and "EDCA", the LCS is "A" (or D or C), return 1For "ABCD" and "EACB", the LCS is "AC", return 2

题目里说了：

ClarificationWhat's the definition of Longest Common Subsequence?

*(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.

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

2. D[i][j]当char i == char j， 可以有三种选择，D[i - 1][j - 1] + 1，D[i ][j - 1], D[i - 1][j] ，取最大的

当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         int[][] res = new int[A.length()+1][B.length()+1]; 9         for (int i=1; i<=A.length(); i++) {10             for (int j=1; j<=B.length(); j++) {11                 res[i][j] = Math.max(A.charAt(i-1)==B.charAt(j-1)? res[i-1][j-1]+1 : res[i-1][j-1], 12                 Math.max(res[i-1][j], res[i][j-1]));13             }14         }15         return res[A.length()][B.length()];16     }17 }