Longest Common Subsequence

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

Your code should return the length of LCS.

Have you met this question in a real interview? 

Yes

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

public class Solution {

    /**

     * @param A, B: Two strings.

     * @return: The length of longest common subsequence of A and B.

     */

    public int longestCommonSubsequence(String A, String B) {

        // write your code here

        int m = A.length(), n = B.length();

        int[][] dp = new int[m+1][n+1];

        for(int i = 0; i < m; i++){

            for(int j = 0; j < n; j++){

                if(A.charAt(i) == B.charAt(j)){

                    dp[i+1][j+1] = dp[i][j] + 1;

                }

                dp[i+1][j+1] = Math.max(dp[i+1][j+1], Math.max(dp[i][j+1], dp[i+1][j]));

            }

           

        }

        return dp[m][n];

    }

}