You want to turn the string word1 into the string word2, one letter at a time. Each step is one of three edits:
Return the fewest edits that turn word1 into exactly word2.
Change the u into w (flowr), then insert an e before the r (flower). One edit is not enough: the lengths differ, so it would have to be an insertion, and no single insertion into flour gives flower.
Delete the leading s (pot) and insert an s at the end (pots). Changing letters in place would need four edits.
cart → mart (change c to m) → marc (change t to c) → march (insert h).
Constraints
0 <= word1.length, word2.length <= 500word1 and word2 are made of lowercase English letters only.Compare the words from the front. If the first letters match, they cost nothing and you move on. If not, one of the three edits has to deal with that first letter of word1 or of word2: try all three and keep the cheapest.
2