Edit distance (Levenshtein distance) powers spell checkers, DNA alignment and diff tools. It is the archetypal 2D DP: the state is a pair of prefixes and each transition is one edit.
Given two strings word1 and word2, return the minimum number of operations required to convert word1 into word2. The allowed operations are: insert a character, delete a character, replace a character.
Examples
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: horse -> rorse (replace h with r) -> rose (delete r) -> ros (delete e)
Input: word1 = "intention", word2 = "execution"
Output: 5
Constraints
0 <= len(word1), len(word2) <= 500, lowercase letters only- Target: O(m * n) time
Goals
- Design a 2D DP whose transitions correspond to three different edit operations
- Handle base cases where one string is empty (all inserts or all deletes)
- Explain each cell of a DP table in words before writing the code