72. 编辑距离

72. 编辑距离 - 力扣（LeetCode）

学习

chatgpt对话
https://chatgpt.com/share/672cf317-1db4-8002-88ab-097738bce5b1

代码

func minDistance(word1 string, word2 string) int {
    if len(word1) == 0 || len(word2) == 0 {
        return max(len(word1), len(word2))
    }

    dp := make([][]int, len(word1)+1)

    for i := range dp {
        dp[i] = make([]int, len(word2)+1)
        dp[i][0] = i
    }

    for j := range dp[0] {
        dp[0][j]= j
    }

    for i:=1;i<len(dp);i++ {
        for j:=1;j<len(dp[i]);j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])+1
            }
        }
    }

    return dp[len(word1)][len(word2)]
}

关键在于填表

这个解法能打败50%，还有其他的解法，灵神的视频讲解的很清楚： 最长公共子序列 编辑距离_哔哩哔哩_bilibili