2D DP
Two strings
Why it matters
Diff tools, DNA alignment, and spell suggestions compare two sequences while allowing items to be skipped. Enumerating subsequences is exponential, and greedy matching can sacrifice a longer alignment later. The exact longest shared subsequence length must be found without generating either string's subsequences.
Real-world constraint
How a diff decides what changed
When you compare two versions of a file, diff tools treat each file as a sequence of lines and find the longest common subsequence of lines, using faster algorithms built on the same idea. Lines in that subsequence are unchanged. Every other line is shown as removed from the old file or added in the new one.
Example
Longest Common Subsequence
Return the length of the longest subsequence common to text1 and text2.
- Input
- text1 = "abcde", text2 = "ace"
- Output
- 3
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Longest Common Subsequence
text1 = "abcde", text2 = "ace"→3
The baseline, Try both drops recursively, is O(2^(m + n)) · O(m + n). The better model below keeps this exact input and removes that bottleneck.
For "abcde" and "ace", brute recursion branches at mismatches and revisits the same position pairs. Fill each prefix pair once: matches a, c, and e extend diagonal values, while mismatches keep the better upper or left value, yielding 3.
For "abcde" and "ace", row 0 and column 0 represent empty prefixes and stay 0. The matching a sets the first match cell to diagonal 0 + 1 = 1. At mismatches such as b versus c, copy the larger value from above or left.
When c meets c, its cell becomes the diagonal value 1 + 1 = 2. When e meets e, it becomes 2 + 1 = 3. Filling every prefix pair this way leaves dp[5][3] = 3, and the diagonal match cells spell "ace".
Visual anchor
Longest Common Subsequence
readingwriting
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.