Woodstock Blog

a tech blog for general algorithmic interview questions

[LintCode] Longest Common Subsequence

Question

link

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

Analysis

This is one of the 2 most popular questions of DP.

This is a two-sequences Dp. The equation is not difficult to build. (consider only the last element of the DP array when building the state transition equation)

Code

public int longestCommonSubsequence(String A, String B) {
    // write your code here
    if (A == null || B == null) {
        return 0;
    }
    int m = A.length(), n = B.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (A.charAt(i - 1) == B.charAt(j - 1)) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}