77. Longest Common Subsequence

LintCode Dynamic Programming Classic

Given two strings, find the longest common subsequence (LCS). Your code should return the length of LCS.

The definition of Longest Common Subsequence [wiki]:

the longest subsequence common to all sequences in a set of sequences (often just two sequences). Unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences.

Example:

For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.
For "ABCD" and "EACB", the LCS is "AC", return 2.

分析¶

这道题可以用动态规划解决。定义 $c[i, j]$ 表示 $X_i$ 和 $Y_j$ 的最长公共子序列的长度，可得如下公式：

LintCode77

public int longestCommonSubsequence(String A, String B) {
    int n = A.length(), m = B.length();
    int lcs[][] = new int[n + 1][m + 1];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(A.charAt(i - 1) == B.charAt(j - 1))
                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[n][m];
}