Dynamic Programming · 039Hard
Edit Distance
Given two strings word1 and word2, return the minimum number of operations to convert word1 into word2. Permitted operations: insert, delete, replace a character.
Constraints
- 0 <= word1.length, word2.length <= 500
- Both consist of lowercase English letters.
Examples
minDistance("horse", "ros") -> 3
minDistance("intention", "execution") -> 5
minDistance("", "abc") -> 3 // three inserts
minDistance("abc", "") -> 3 // three deletes
minDistance("abc", "abc") -> 0 // already equal
minDistance("kitten", "sitting") -> 3 // replace, replace, insertEdge cases
- Either string empty — the answer is the other's length.
- Identical strings cost 0.
- All three operations cost exactly 1.
Show the target complexity (spoiler)
- Naive
- O(3^n) time — recurse over every operation at every position.
- Target
- O(m * n) time and space (reducible to O(min(m, n))) — the Levenshtein DP grid.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/09-dynamic-programming/039-edit-distance.js ./practice c 039