LeetCode 1143 · Medium · 2-D Dynamic Programming

Longest Common Subsequence

Given two strings, return the length of the longest sequence of characters that appears in both, in the same order but not necessarily side by side. No common character means 0.

O(m·n)time
O(m·n)space
match → diagonalelse max(right, down)

lowercase letters a–z · 1–8 characters each

dp dp[i][j] = LCS of text1.substring(i) and text2.substring(j) · ∅ = nothing left

public int longestCommonSubsequence(String text1, String text2) { int m = text1.length(), n = text2.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = m - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { if (text1.charAt(i) == text2.charAt(j)) { dp[i][j] = 1 + dp[i + 1][j + 1]; } else { dp[i][j] = Math.max(dp[i][j + 1], dp[i + 1][j]); } } } return dp[0][0];}
i, j
—
text1.charAt(i)
—
text2.charAt(j)
—
dp[i][j]
—

Why it works

  1. Brute force lists every subsequence of one string (2m of them) and checks each against the other in O(n): O(n·2m).
  2. Look at the first characters. If text1.charAt(i) == text2.charAt(j), some longest answer uses that pair, so take it and move both: 1 + dp[i+1][j+1]. If not, one of them is useless here: drop either and keep the better, max(dp[i][j+1], dp[i+1][j]).
  3. Fill from the bottom-right. Each cell reads the cell to its right, below, and diagonally below-right, all filled earlier. (m+1)·(n+1) cells, O(1) each: O(m·n) time and space. Keeping only two rows cuts space to O(n).
  4. Pitfall: the extra ∅ row and column. They stand for an empty suffix, whose LCS with anything is 0, and they keep i + 1 and j + 1 inside the table.
  5. Getting the subsequence itself: walk from dp[0][0]. On a match take the character and go diagonal; otherwise step toward the larger neighbour. The green path in the last step does exactly that.
  6. Related: Edit Distance (72) and Distinct Subsequences (115) use the same two-suffix table with a different rule per cell.