72. Edit Distance
You are given two lowercase strings word1 and word2 (either may be empty). In a single operation you may pick any one of:
- insert one character anywhere in
word1, - delete one character from
word1, - replace one character of
word1with any other character.
Return the minimum number of operations required to transform word1 into word2, as an integer. This quantity is the classic Levenshtein distance between the two strings.
Example 1:
Input: word1 = "kitten", word2 = "sitting"
Output: 3
Explanation: Replace 'k' with 's' ("sitten"), replace 'e' with 'i' ("sittin"), then insert 'g' at the end ("sitting") — 3 operations, and no shorter sequence exists.
Example 2:
Input: word1 = "flaw", word2 = "lawn"
Output: 2
Explanation: Delete the leading 'f' ("law") and insert 'n' at the end ("lawn").
Constraints:
- 0 ≤ word1.length, word2.length ≤ 500
- word1 and word2 consist of lowercase English letters
Hints:
Compare prefixes. Define f(i, j) = fewest edits to turn the first i characters of word1 into the first j characters of word2. If the two last characters match, they cost nothing: f(i, j) = f(i-1, j-1).
When the last characters differ you have exactly three moves, each costing 1: replace (reduces to f(i-1, j-1)), delete the last char of the prefix (f(i-1, j)), or insert the needed char (f(i, j-1)). Take the cheapest. Base cases: turning an i-char prefix into the empty string costs i deletions, and building a j-char prefix from nothing costs j insertions. Fill the (m+1)×(n+1) table row by row.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: word1 = "kitten", word2 = "sitting"
Expected output: 3