Given two strings, find the longest common subsequence (LCS).
Your code should return the length of LCS.
Example
For "ABCD"
and "EDCA"
, the LCS is "A"
(or "D"
, "C"
), return 1
.
For "ABCD"
and "EACB"
, the LCS is "AC"
, return 2
.
Clarification
What’s the definition of Longest Common Subsequence?
- https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
- http://baike.baidu.com/view/2020307.htm
Solution: Dynamic Programming
public int longestCommonSubsequence(String A, String B) { if (A == null || A.length() == 0 || B == null || B.length() == 0) { return 0; } int[][] lcs = new int[A.length()][B.length()]; for (int i = 0; i < A.length(); i++) { for (int j = 0; j < B.length(); j++) { if (i == 0 || j == 0) { lcs[i][j] = A.charAt(i) == B.charAt(j) ? 1 : 0; } else { if (A.charAt(i) == B.charAt(j)) { lcs[i][j] = lcs[i - 1][j - 1] + 1; } else { lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]); } } } } return lcs[A.length() - 1][B.length() - 1]; }