> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dynamic-programming/72.-edit-distance.md).

# 72. Edit Distance

Given two words *word1* and *word2*, find the minimum number of operations required to convert *word1* to *word2*.

You have the following 3 operations permitted on a word:

1. Insert a character
2. Delete a character
3. 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')
```

{% hint style="info" %}
這題所求可以從中間過程的子問題來得到，所以用DP來做。dist\[i]\[j]代表把word1\[0...i - 1]轉變成word2\[0...j - 1]所需要的操作次數。\
dp state transition:\
dp\[i]\[j] = dp\[i - 1]\[j - 1] if word1\[i - 1] == word2\[j - 1]\
dp\[i]\[j] = min(dp\[i - 1]\[j], dp\[i]\[j - 1], dp\[i - 1]\[j - 1]) + 1 if word1\[i - 1] != word2\[j - 1]
{% endhint %}

```cpp
// Dynamic Programming
int minDistance(string word1, string word2) { // time: O(m*n); space: O(m*n)
    int m = word1.size(), n = word2.size();
    // dist[i][j] means the number of operations required to convert word1[0...i-1] to word2[0...j-1]
    vector<vector<int> > dist(m + 1, vector<int>(n + 1, 0));
    for (int j = 1; j <= n; ++j)
        dist[0][j] = j;
    for (int i = 1; i <= m; ++i) {
        dist[i][0] = i;
        for (int j = 1; j <= n; ++j) {
            if (word1[i - 1] != word2[j - 1])
                dist[i][j] = min({dist[i - 1][j], dist[i][j - 1], dist[i - 1][j - 1]}) + 1;
            else
                dist[i][j] = dist[i - 1][j - 1];
        }
    }
    return dist.back().back();
}
```

{% hint style="info" %}
但因為dp table中每個grid只跟上方、左邊、左上的grid有關，所以可以用1-D dp array去紀錄搭配其他變數就能完成。
{% endhint %}

```cpp
// Space Optimized Dynamic Programming
int minDistance(string word1, string word2) { // time: O(m*n); space: O(n)
    int m = word1.size(), n = word2.size();
    // dist[i][j] means the number of operations required to convert word1[0...i-1] to word2[0...j-1]
    vector<int> dist(n + 1, 0);
    for (int j = 1; j <= n; ++j)
        dist[j] = j;
    for (int i = 1; i <= m; ++i) {
        int upper_left = dist[0];
        dist[0] = i; // initialize the first column
        for (int j = 1; j <= n; ++j) {
            int upper = dist[j];
            if (word1[i - 1] != word2[j - 1])
                dist[j] = min({dist[j], dist[j - 1], upper_left}) + 1;
            else
                dist[j] = upper_left;
            upper_left = upper;
        }
    }
    return dist.back();
}
```