Edit Distance
Given two strings word1 and word2, return the minimum number of operations required to convert word1 into word2.
You may perform the following operations on word1:
- Insert a character.
- Delete a character.
- Replace a character.
Example 1
Input
word1 = "horse", word2 = "ros"Output
3Replace 'h' with 'r', delete the second 'r', and delete 'e' to transform "horse" into "ros" in 3 operations.
Example 2
Input
word1 = "intention", word2 = "execution"Output
5Delete 'd', replace 'i' with 'e', insert 'c', replace 'u' with 'x', and insert 'n' to transform "intention" into "execution" in 5 operations.
Constraints
- 0 <= word1.length, word2.length <= 500
- word1 and word2 consist of lowercase English letters