loading

Longest Common Subsequence — Step-by-Step Visualization

mediumLeetCode #1143StringDynamic Programming

Given two strings `text1` and `text2`, return the length of their longest common subsequence. If there is no common subsequence, return 0. A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Algorithm Pattern

2D Dynamic Programming

Key Idea

We build a 2D matrix `dp[i][j]` representing the length of the longest common subsequence of `text1[i:]` and `text2[j:]`. - If `text1[i] == text2[j]`, then `dp[i][j] = 1 + dp[i+1][j+1]` (Characters match, move diagonally). - If `text1[i] != text2[j]`, then `dp[i][j] = max(dp[i+1][j], dp[i][j+1])` (Mismatch, try skipping one character from either string).

Step-by-Step Approach

  1. Initialize a `(len(text1)+1) x (len(text2)+1)` matrix with zeros.
  2. Iterate backwards from the bottom-right of the matrix.
  3. If characters match: `dp[i][j] = 1 + dp[i+1][j+1]`.
  4. If characters mismatch: `dp[i][j] = max(dp[i+1][j], dp[i][j+1])`.
  5. Return `dp[0][0]`.

Common Gotchas

  • The order of iteration can be forward or backward, but the base cases (empty strings) are usually defined at the edges.
  • O(m*n) time and space complexity.

Related Problems

← All problems