72. 编辑距离

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符

思路

  1. 动态规划
  2. 定义 dp[i][j]
    21. dp[i][j] 代表 word1 中前 i 个字符，变换到 word2 中前 j 个字符，最短需要操作的次数
    22. 需要考虑 word1 或 word2 一个字母都没有，即全增加/删除的情况，所以预留 dp[0][j] 和 dp[i][0]

`

`

  1. 状态转移
    31. 增，dp[i][j] = dp[i][j - 1] + 1
    32. 删，dp[i][j] = dp[i - 1][j] + 1
    33. 改，dp[i][j] = dp[i - 1][j - 1] + 1
    34. 按顺序计算，当计算 dp[i][j] 时，dp[i - 1][j] ， dp[i][j - 1] ， dp[i - 1][j - 1] 均已经确定了
    35. 配合增删改这三种操作，需要对应的 dp 把操作次数加一，取三种的最小
    36. 如果刚好这两个字母相同 word1[i - 1] = word2[j - 1] ，那么可以直接参考 dp[i - 1][j - 1] ，操作不用加一
  1. //二维动规，时空都是O(m*n)
  2. func minDistance(word1 string, word2 string) int {
  3.     m, n := len(word1), len(word2)
  4.     dp := make([][]int, m+1)
  6.     for i := range dp {
  7.         dp[i] = make([]int, n+1)
  8.     }
  10.     for i := 0; i <= m; i++ {                //1， 初始化dp数组
  11.         dp[i][0] = i            // word1[i] 变成 word2[0], 删掉 word1[i], 需要 i 部操作
  12.     }
  13.     for j := 0; j <= n; j++ {
  14.         dp[0][j] = j            // word1[0] 变成 word2[j], 插入 word1[j]，需要 j 部操作
  15.     }
  17.     for i := 1; i <= m; i++ {                //2， 递归求最小值到dp[m][n]
  18.         for j := 1; j <= n; j++ {
  19.             if word1[i-1] == word2[j-1] {
  20.                 dp[i][j] = dp[i-1][j-1]
  21.             } else {                        // Min(插入，删除，替换)
  22.                 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1    
  23.             }
  24.         }
  25.     }
  26.     return dp[m][n]
  27. }
  29. func min(args ...int) int {
  30.     Min := args[0]
  31.     for _, v := range args {
  32.         if v < Min {
  33.             Min = v
  34.         }
  35.     }
  36.     return Min
  37. }
//滚动数组，压缩成一维dp，空间O(max(m,n)
func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([]int, max(m,n)+1)           //避免数组越界，必须写，不然会报错空间不足

    for i := range dp {
        dp[i] = i                           //base case init
    }

    for i := 1; i <= m; i++ {
        temp := dp[0]
        dp[0] = i

        for j := 1; j <= n; j++ {
            pre := temp  
            temp = dp[j]

            if word1[i-1] == word2[j-1] {
                dp[j] = pre
            } else {                        // Min(插入，删除，替换)
                dp[j] = min(dp[j], dp[j-1], pre) + 1    
            }
        }
    }
    return dp[n]
}

func min(args ...int) int {
    Min := args[0]
    for _, item := range args {
        if item < Min {
            Min = item
        }
    }
    return Min
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}