首页 > 代码库 > LintCode-Longest Common Subsequence
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
Solution:
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 int lenA = A.length(), lenB = B.length(); 8 if (lenA==0 || lenB == 0) return 0; 9 10 int[][] lcs = new int[lenA+1][lenB+1];11 for (int i=0;i<=lenA;i++) lcs[i][0] = 0;12 for (int i=0;i<=lenB;i++) lcs[0][i] = 0;13 14 for (int i=1;i<=lenA;i++)15 for (int j=1;j<=lenB;j++){16 lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);17 if (A.charAt(i-1) == B.charAt(j-1) && lcs[i][j]<lcs[i-1][j-1]+1)18 lcs[i][j] = lcs[i-1][j-1]+1;19 }20 21 return lcs[lenA][lenB];22 }23 }
LintCode-Longest Common Subsequence
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。