Edit Distance
Problem Description
Given two strings word1 and word2, return the minimum number of operations (insert, delete, replace) to convert word1 to word2.
Example 1:
Input: word1="horse", word2="ros"
Output: 3 (horse→rorse→rose→ros)
Example 2:
Input: word1="intention", word2="execution"
Output: 5
DE Shaw Tier 3 — LC 72.
DP O(m*n): dp[i][j] = edit distance between word1[0..i-1] and word2[0..j-1].
If chars match: dp[i][j] = dp[i-1][j-1].
Else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) (delete, insert, replace).
Example Test Cases
Example 1
Input: ["horse","ros"]
Expected: 3
Example 2
Input: ["intention","execution"]
Expected: 5
Example 3
Input: ["","a"]
Expected: 1
Example 4
Input: ["abc","abc"]
Expected: 0
Run your code to see the results