# 0072. Edit Distance

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Edit Distance](https://leetcode.com/problems/edit-distance/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0072-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
  {% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

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

```
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
    horse -> rorse (replace 'h' with 'r')
    rorse -> rose (remove 'r')
    rose -> ros (remove 'e')

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')
```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
We **simulate and figure out the cost** of the following four operations:

* **Delete** = 1 modification (Delete char in word1)\
  **Move to the next char in word1 to compare.**\
  So we take **`table[i-1][j]`**<br>
* **Insert** = 1 modification (Insert char to word1)\
  **Move to the next char in word2 to compare.**\
  So we take **`table[i][j-1]`**<br>
* **Replace** = 1 modification (Replace the char in word1)\
  **Move to the next char in both word1 and word2 to compare.**\
  So we take **`table[i-1][j-1]`**<br>
* **Skip** = 0 modification (Two chars are the same)\
  **Move to the next char in both word1 and word2 to compare.**\
  So we take **`table[i-1][j-1]`**
  {% endhint %}

We create a **2D array** and initialize values on **`table[i][0]`** and **`table[0][j]`**

Then iterate through each char by the nested for loops to find the minimum operations.\
\&#xNAN;**`i in range(1, len(word1) + 1)`**\
\&#xNAN;**`j in range(1, len(word2) + 1)`**
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # (base case)
        if not word1 and not word2: return 0
        if not word1 or not word2: return len(word1) + len(word2)

        # ==================================================
        #  String + Dynamic Programming                    =
        # ==================================================
        # time  : O(mn)
        # space : O(mn)
        
        table = [[0] * (len(word2) + 1) for _ in range(len(word1) + 1)]
        for i in range(len(word1) + 1): table[i][0] = i
        for j in range(len(word2) + 1): table[0][j] = j
        
        '''
        [[0, 1, 2, 3], 
         [1, 0, 0, 0], 
         [2, 0, 0, 0], 
         [3, 0, 0, 0], 
         [4, 0, 0, 0], 
         [5, 0, 0, 0]]
         '''
        
        for i in range(1, len(word1) + 1):
            for j in range(1, len(word2) + 1):
                if word1[i - 1] == word2[j - 1]: table[i][j] = table[i-1][j-1]
                else:
                    table[i][j] = 1 + min(table[i-1][j], table[i][j-1], table[i-1][j-1])
        
        return table[-1][-1]
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**  
     * @time  : O(mn)
     * @space : O(mn)
     */
     
    String word1, word2;
    int n1, n2;
    int[][] table;
    
    public int minDistance(String word1, String word2) {
        /* base case */
        if(word1 == null && word2 == null) return 0;
        if(word1 == null || word2 == null) return word1.length() + word2.length();
        
        this.word1 = word1;
        this.word2 = word2;
        this.n1 = word1.length();
        this.n2 = word2.length();
            
        this.table = new int[word1.length()][word2.length()];
        for(int i=0 ; i<word1.length() ; i++) {
            Arrays.fill(this.table[i], -1);
        }
        
        return dp(0, 0);
    }
    
    public int dp(int index1, int index2) {
        if(index1 == this.n1) return this.n2 - index2;
        if(index2 == this.n2) return this.n1 - index1;
        
        if(this.table[index1][index2] != -1) return this.table[index1][index2];
        
        if(this.word1.charAt(index1) == this.word2.charAt(index2)) {
            this.table[index1][index2] = dp(index1 + 1, index2 + 1);
            
        } else {
            int insert  = 1 + dp(index1,     index2 + 1);
            int delete  = 1 + dp(index1 + 1, index2);
            int replace = 1 + dp(index1 + 1, index2 + 1);
            
            this.table[index1][index2] = Math.min(Math.min(insert, delete), replace);
        }
        
        return this.table[index1][index2];
    }
}
```

{% endtab %}
{% endtabs %}