Edit Distance
MediumDynamic Programming
You are given two strings word1 and word2. You may change word1 using these operations, each costing 1:
- Insert one character anywhere.
- Delete one character.
- Replace one character with a different character.
Return the minimum number of operations needed to turn word1 into word2.
Example 1
- Input:
- word1 = "kitten", word2 = "sitting"
- Output:
- 3
- Explanation
- Replace
kwiths, replaceewithi, and insertgat the end. Fewer than 3 is impossible.
Example 2
- Input:
- word1 = "flaw", word2 = "lawn"
- Output:
- 2
- Explanation
- Delete the leading
fto getlaw, then insertnat the end.
Example 3
- Input:
- word1 = "abc", word2 = ""
- Output:
- 3
- Explanation
- Turning a word into the empty string takes one deletion per character.
Constraints
- 0 ≤
word1.length,word2.length≤ 500 word1andword2consist of lowercase English letters