Edit Distance
Calculate the minimum number of operations (insert, delete, replace) required to convert one string into another.
Ready
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
Think of it as the "cost" to transform one word into another. If characters match, it costs nothing. If they differ, you pay a price for an operation (Insert, Delete, or Replace). We want to find the cheapest path involves checking all three possibilities at each step.
Concept
2D Dynamic Programming:
We define `dp[i][j]` as the edit distance between the first `i` characters of word1 and the first `j` characters of word2.
Recurrence Relation:
- Match (word1[i] == word2[j]): `dp[i-1][j-1]` (No op needed).
- Mismatch (word1[i] != word2[j]): `1 + min(Insert, Delete, Replace)`
- Insert: `dp[i][j-1]`
- Delete: `dp[i-1][j]`
- Replace: `dp[i-1][j-1]`
How it Works
Tabulation Algorithm:
- Initialize `dp` table of size (m+1) \times (n+1).
- Base Cases: First row (transform to empty string) = `j`. First column (transform from empty string) = `i`.
- Iterate i from 1 to m, j from 1 to n.
- Apply recurrence relation.
- Result is `dp[m][n]`.
Step-by-Step Breakdown
Visualizing the Table:
- Diagonal Move (No Cost): Match found.
- Diagonal Move (Cost 1): Replacement.
- Left Move (Cost 1): Insertion.
- Up Move (Cost 1): Deletion.
When to Use
Applications:
- Spell checkers (Levenshtein distance).
- DNA sequence alignment (mutation analysis).
- Plagiarism detection.
When NOT to Use
- Simple Matches: If only exact matches matter.
- Restricted Ops: If only insertions/deletions allowed, it's simpler (related to LCS).
How to Identify
"Minimum operations to convert...", "Levenshtein distance".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.