Edit Distance
Medium· 2D DP· LCS
Problem
Given two words, find the minimum number of single-character edits needed to turn the first into the second. An edit is inserting, deleting, or replacing one character.
Examples
Input: word1 = "horse", word2 = "ros"
Output: 3
Replace h→r, delete r, delete e.
Input: word1 = "intention", word2 = "execution"
Output: 5
Constraints
- • 0 <= word1.length, word2.length <= 500
- • Only lowercase English letters
Hints & approach
Hint 1
Turning a string into the empty string costs its length.
Hint 2
If the last characters match, no edit is needed for them.
Hint 3
Otherwise take 1 + min(insert, delete, replace) from the three neighbouring states.
Approachtry the hints first
Let dp[i][j] be the edits needed to turn the first i characters of word1 into the first j of word2. Base cases: dp[i][0] = i (delete all) and dp[0][j] = j (insert all). If word1[i-1] equals word2[j-1], dp[i][j] = dp[i-1][j-1]. Otherwise dp[i][j] = 1 + min(dp[i-1][j] for delete, dp[i][j-1] for insert, dp[i-1][j-1] for replace). Two rows are enough.
Time O(m·n) · Space O(n)