Edit Distance

## Problem Given two strings `word1` and `word2`, return the **minimum number of operations** required to convert `word1` to `word2`. You have the following three operations permitted on a word: - **Insert** a character - **Delete** a character - **Replace** a character ## Examples **Example 1:** ``` Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') ``` **Example 2:** ``` Input: word1 = "intention", word2 = "execution" Output: 5 ``` **Example 3:** ``` Input: word1 = "abc", word2 = "abc" Output: 0 ``` ## Approach Hints Use 2D dynamic programming. Let `dp[i][j]` = min operations to convert `word1[0..i-1]` to `word2[0..j-1]`. If characters match, `dp[i][j] = dp[i-1][j-1]`. Otherwise, `dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])`.