> For the complete documentation index, see [llms.txt](https://leetcodebook-1.gitbook.io/top-interview-150/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcodebook-1.gitbook.io/top-interview-150/dynamic/edit-distance.md).

# 编辑距离

题目链接: <https://leetcode.cn/problems/edit-distance/>

## 解题思路：

1. 设定二维数组dp\[i]\[j],表示word1\[i]转变到word2\[j]需要的最少步数
2. word1\[i]==word2\[j] dp\[i]\[j]=dp\[i-1]\[j-1]
3. word1\[i]!=word2\[j] dp\[i]\[j]=min(dp\[i-1]\[j-1],dp\[i-1]\[j],dp\[i]\[j-1])+1
4. dp\[i-1]\[j-1]表示替换，dp\[i-1]\[j]表示删除，dp\[i]j-1]表示插入
5. dp\[0]\[j]需要特殊处理，代表word1是"",变成word2的最少步骤，插入步骤，插入word2长度
6. dp\[i]\[0]需要特殊处理，代表把word1从原字符串变成word2为空的最少步骤，删除步骤，删除word1长度

```go
func minDistance(word1 string, word2 string) int {
    l1,l2 := len(word1),len(word2)
    dp := make([][]int,l1+1)
    for i:=0;i<l1+1;i++{
        dp[i]=make([]int,l2+1)
    }
    for i:=0;i<=l1;i++{
       dp[i][0]=i
    }
    for j:=0;j<=l2;j++{
        dp[0][j]=j
    }
    for i:=1;i<=l1;i++{
        for j:=1;j<=l2;j++{
            if word1[i-1]==word2[j-1]{
                dp[i][j]=dp[i-1][j-1]
            }else{
                dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1
            }
           
        }
    }
    return dp[l1][l2]
}
func min(a,b int) int {
    if a<b{
       return a
    }
    return b
}

```

## 复杂度分析

* **时间复杂度：** 时间复杂度是 $$O(l1\*l2)$$，其中 $$l1$$ 是字符串 `word1` 的长度, $$l2$$ 是字符串 `word2` 的长度
* **空间复杂度：** 空间复杂度是 $$O(l1\*l2)$$，我们需要一个l1\*l2二维数组存储每个位置的状态。