Edit Distance
Part of Practice: Prefix & Memo DP
Given two strings word1 and word2, return the minimum number of single-character operations needed to turn word1 into word2. Three operations are allowed: insert a character, delete a character, or replace a character. This count is known as the Levenshtein distance.
Constraints: 0 <= word1.length, word2.length <= 500, lowercase English letters.
Examples
- Input:
- word1 = "horse", word2 = "ros"
- Output:
- 3
horse -> rorse (replace h with r) -> rose (delete r) -> ros (delete e).
- Input:
- word1 = "intention", word2 = "execution"
- Output:
- 5
- Input:
- word1 = "", word2 = "abc"
- Output:
- 3
Insert all three characters.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.