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]; }