Lintcode: Longest Common Subsequence
3710 ワード
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 }