> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/wan-quan-an-zhao-jiu-zhang-suan-fa-shua-de-60-dao-zuo-you/ix.-dynamic-programming/72.-edit-distance.md).

# 72. Edit Distance

\# Hard （非常经典，一定要会）

{% hint style="info" %}
典型的二维序列DP问题，即需要一个二维数组来记录关键信息，这道题经常考
{% endhint %}

### Solution:

1. Initilize `minDis[i][j]`, 这种一定是初始化横行和纵行。`minDis[i][j]` means the minimum distance of converting from `word1[:i+1]` to `word2[:j+1]`. One extra empty element in `minDis` is very necessary, because following elements are based on the previous elemens.
2. Three cases may affect minDis.

   1. `minDis[i-1][j]` + 1 次转换
   2. `minDis[i][j-1]` + 1 次转换
   3. `word1[i-1] = word2[j-1]`, 所以不用转换, `minDis[i-1][j-1]`

   从中找一个最小值赋值给`minDis[i][j]`即可。

{% tabs %}
{% tab title="Python" %}

```python
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # two-sequence DP problem
        # initialize minDis, minDis[i][j] means min distance from word1[:i+1] to word2[:j+1]
        minDis = [[float('Inf')]*(len(word2)+1) for i in range(len(word1)+1)]

        for i in range(len(word1)+1):
            minDis[i][0] = i
        for j in range(len(word2)+1):
            minDis[0][j] = j
            
        # compute
        for i in range(1, len(word1)+1):
            for j in range(1, len(word2)+1):
                minDis[i][j] = min(minDis[i-1][j], minDis[i][j-1]) + 1
                if word1[i-1] == word2[j-1]:
                    minDis[i][j] = min(minDis[i][j], minDis[i-1][j-1])
                else:
                    minDis[i][j] = min(minDis[i][j], minDis[i-1][j-1]+1)
        
        return minDis[len(word1)][len(word2)]p
```

{% endtab %}

{% tab title="Java(O(mn))" %}

```java
class Solution {
    public int minDistance(String word1, String word2) {
        int[][] minDis = new int[word1.length()+1][word2.length()+1];
        for(int i = 0; i <= word1.length(); i ++)
            minDis[i][0] = i;
        for(int j = 0; j <= word2.length(); j ++)
            minDis[0][j] = j;
        
        for(int i = 1; i <= word1.length(); i ++)
            for(int j = 1; j <= word2.length(); j ++) {
                int temp = Math.min(minDis[i-1][j], minDis[i][j-1]) + 1;
                if(word1.charAt(i-1) == word2.charAt(j-1))
                    minDis[i][j] = Math.min(temp, minDis[i-1][j-1]);
                else
                    minDis[i][j] = Math.min(temp, minDis[i-1][j-1]+1);
            }
        return minDis[word1.length()][word2.length()];
    }
}
```

{% endtab %}
{% endtabs %}