Longest Common Subsequence

Question (LC.77)

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

Example

I: "ABCD", "EDCA"
O: len("A") = 1
I: "ABCD", "EACB"
O: len("AB") = 2

Analysis

The classic two sequence DP. Draw a grid then tabulation.

Approach

1. Define (optimal) subproblems
LCS(i,j) = longest common subsequence from A[:i] and B[:j]

2. Solve by prefix
if (A[i] == B[j])
    LCS(i,j) = LCS(i-1,i-j) + 1
else
    LCS(i,j) = Math.max(LCS(i,j-1), LCS(i-1,j))

3. Topo order
for i from 1 to n
    for j from 1 to m

4. Init base
for i from 0 to n
    LCS(i,0) = 0
for j from 0 to m
    LCS(0,j) = 0

5. Final answer
LCS(n,m)

Code

public int longestCommonSubsequence(String A, String B) {
    if (A == null || B == null) {
        return -1;
    }
    int n = A.length(), m = B.length();
    // create memo table
    int[][] memo = new int[n+1][m+1];
    // init base, java init 0
    // topo order
    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < m + 1; j++) {
            if (A.charAt(i-1) == B.charAt(j-1)) {
                memo[i][j] = memo[i-1][j-1] + 1;
            } else {
                memo[i][j] = Math.max(memo[i][j-1], memo[i-1][j]);
            }
        }
    }
    // final answer
    return memo[n][m];
}

Time Complexity

#subproblems * time/subproblem = O(m*n) * O(1) = O(mn)