Lintcode: Longest Common Subsequence

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



Your code should return the length of LCS.



Example

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



For "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]はs 1,s 2の前i,j文字列の最長common subsequenceとして定義.
2.D[i][j]char i==char jの場合、3つの選択肢があり、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]に大きな(最後の文字が異なるため、s 1の最後の文字がs 2の前の部分に現れる可能性があり、逆も同様である.

 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 }