Edit Distance (Levenshtein Distance)

# Edit Distance (Levenshtein Distance) ## Difficulty Medium ## Tags `dynamic programming`, `string` ## Problem Statement Given two strings `word1` and `word2`, return the minimum number of operations required to convert `word1` to `word2`. You have three operations permitted on a word: - **Insert** a character - **Delete** a character - **Replace** a character ## Constraints - 0 ≤ word1.length, word2.length ≤ 500 - Both strings consist of lowercase English letters. ## Signatures ### Python ```python def min_distance(word1: str, word2: str) -> int: pass ``` ### Java ```java public class Solution { public int min_distance(String word1, String word2) { return null; } } ``` ### Csharp ```csharp public class Solution { public int min_distance(string word1, string word2) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: int min_distance(string word1, string word2) { } }; ``` ### C ```c int min_distance(char* word1, char* word2) { } ``` ### Ruby ```ruby def min_distance(word1, word2) end ``` ### Perl ```perl sub min_distance { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def min_distance(word1: String, word2: String): Int = { } } ``` ### Haskell ```haskell min_distance :: ... -> ... min_distance args = undefined ``` ### Clojure ```clojure (defn min_distance [word1 word2] ) ``` ### Scheme ```scheme (define (min_distance word1 word2) ) ``` ## Examples ### Example 1 **Input:** ``` word1 = "horse" word2 = "ros" ``` **Output:** ``` 3 ``` **Explanation:** 1. horse → rorse (replace 'h' with 'r') 2. rorse → rose (delete 'r') 3. rose → ros (delete 'e') ### Example 2 **Input:** ``` word1 = "intention" word2 = "execution" ``` **Output:** ``` 5 ``` **Explanation:** 1. intention → inention (delete 't') 2. inention → enention (replace 'i' with 'e') 3. enention → exention (replace 'n' with 'x') 4. exention → exection (replace 'n' with 'c') 5. exection → execution (insert 'u') ### Example 3 **Input:** ``` word1 = "" word2 = "abc" ``` **Output:** ``` 3 ``` **Explanation:** Insert 'a', 'b', 'c'. ## Hints 1. Use dynamic programming with a 2D table. 2. `dp[i][j]` = min operations to convert word1[0..i-1] to word2[0..j-1]. 3. If characters match: `dp[i][j] = dp[i-1][j-1]` 4. Otherwise: `dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])` - `dp[i-1][j]` + 1 = delete from word1 - `dp[i][j-1]` + 1 = insert into word1 - `dp[i-1][j-1]` + 1 = replace