Given two strings word1 and word2, return the minimum number of operations needed to turn word1 into word2.
Each operation inserts one character, deletes one character, or replaces one character.
Examples
Example 1
- Input
- word1 = "horse", word2 = "ros"
- Output
- 3
- Why
- horse → rorse (replace h) → rose (delete r) → ros (delete e).
Example 2
- Input
- word1 = "intention", word2 = "execution"
- Output
- 5
Constraints
0 <= word1.length, word2.length <= 500- Both words contain only lowercase English letters.