72.编辑距离

动态规划

f[i][j] 记录 word1[1..i] 到 word2[1..j] 的最短编辑距离。则考虑三种情况：

1. word1插入一个字符和word2相等：f[i][j-1] + 1
2. word1删除一个字符和word2相等： f[i-1][j] + 1
3. word1替换一个字符和word2相等：f[i-1]f[j-1] + eq 。其中eq考虑两种状态，如果word1要替换的这个字符和word2的最后一个字符相等，则表示不需要替换已经相等，eq等0，否则eq等于1

时间复杂度： O(MN)
空间复杂度： O(MN)

func minDistance(word1 string, word2 string) int {
    // f[i][j] = min(f[i][j-1]+1, f[i-1][j]+1, f[i-1][j-1] + eq)

    m := len(word1)
    n := len(word2)
    f := make([][]int, m+1)

    for i := 0; i <= m; i++ {
        f[i] = make([]int, n+1)
        for j := 0; j <= n; j ++ {
            if i == 0 {
                f[i][j] = j
                continue
            }

            if j == 0 {
                f[i][j] = i
                continue
            }

            temp := min(f[i][j-1] + 1, f[i-1][j] + 1)

            eq := 1
            if word1[i-1] == word2[j-1] {
                eq = 0
            }
            temp = min(temp, f[i-1][j-1]+eq)

            // fmt.Printf("f[%v][%v]: %v\n", i, j, temp)

            f[i][j] = temp
        }
    }

    return f[m][n]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}