Edit Distance
Medium · 2-D Dynamic Programming · String · Dynamic Programming
Problem
Given two strings word1 and word2, return the fewest single-character edits that turn word1 into word2. Three edits are allowed, each costing one:
- insert a character,
- delete a character,
- replace a character with a different one.
This number is the *Levenshtein distance*. Either string may be empty: turning "abc" into "" takes three deletions.
Examples
Input: word1 = "horse", word2 = "ros" Output: 3
Replace h with r (rorse), delete the first r (rose), then delete e (ros).
Input: word1 = "intention", word2 = "execution" Output: 5
One shortest route: delete t, replace i with e, replace n with x, replace n with c, insert u.
Constraints
- 0 <= len(word1), len(word2) <= 500
- word1 and word2 consist of lowercase English letters
Approaches
- Memoized recursion from the front — time O(m · n), space O(m · n)
Follow-up
How would you return the edits themselves, not just how many? And if insert, delete and replace had different costs, what in the recurrence would change?
Related problems
Start free on Cariara · Coding problems · System design studio
