# Leetcode 72. Edit Distance

[link](https://leetcode.com/problems/edit-distance)

---

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

#### 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
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

#### Constraints:

- 0 <= word1.length, word2.length <= 500
- word1 and word2 consist of lowercase English letters.

---

Calculate the lengths of both input words (word1 and word2) and initialize a 2D table (dp) to store intermediate results for dynamic programming.

Initialize the last row and last column of the dp table to represent the minimum edit distances required to convert substrings of word1 and word2 into empty strings.

Dynamic Programming: Iterate through the dp table in reverse order (from the bottom-right corner to the top-left corner). For each cell, compare the characters at the corresponding positions in word1 and word2. If they are equal, set the value in the cell to be equal to the value in the diagonal cell (representing no edit required). If they are not equal, calculate the minimum edit distance by considering three possible operations: insertion, deletion, and substitution.

#### Solution 1

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n, m = len(word1), len(word2)        
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        
        for i in range(len(word2) + 1):
            dp[n][i] = m - i
        for j in range(len(word1) + 1):
            dp[j][m] = n - j

        for i in range(n - 1, -1, -1):
            for j in range(m - 1, -1, -1):
                if word1[i] == word2[j]:
                    dp[i][j] = dp[i + 1][j + 1]
                else:
                    dp[i][j] = 1 + min(dp[i + 1][j],
                                         dp[i][j + 1],
                                         dp[i + 1][j + 1])
                    
        return dp[0][0]
        

O(T): O()
O(S): O()