You are given two words, word1 and word2. Change word1 into word2 using as few steps as possible. In one step you can do one of these:
- Insert one character.
- Delete one character.
- Replace one character with another.
Return the smallest number of steps.
Examples
Example 1:
Input: word1 = "sunday", word2 = "saturday"
Output: 3
Explanation: sunday -> saunday (insert a)
saunday -> satunday (insert t)
satunday -> saturday (replace n with r)
Example 2:
Input: word1 = "flaw", word2 = "lawn"
Output: 2
Explanation: flaw -> law (delete f)
law -> lawn (insert n)
Example 3:
Input: word1 = "tea", word2 = ""
Output: 3
Explanation: Delete the three characters one by one.