编辑距离

72. 编辑距离

leetcode 链接

思路：

动态规划

1.确定 dp 数组含义：dp[i][j] 表示 word1 子字符串长度为 i，word2 子字符串长度为 j 的最小编辑距离。

2.初始化 dp 数组，dp[i][0] = i, dp[0][j] = j。

3.确定遍历方向，从前往后遍历。

4.确定转移方程，当 word1[i - 1] == word2[j - 1] 时，dp[i][j] = dp[i - 1][j - 1]。不相等时，dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1)。相当于删除 word1[i - 1] 或者 word2[j - 1]，或者替换操作。

5.返回 dp[word1Len][word2Len] 即可。

typescript 解法

function minDistance(word1: string, word2: string): number {
  const len1: number = word1.length;
  const len2: number = word2.length;

  const dp: number[][] = new Array(len1 + 1)
    .fill(0)
    .map(() => new Array(len2 + 1).fill(0));

  for (let i: number = 0; i <= len1; i++) {
    dp[i][0] = i;
  }
  for (let j: number = 0; j <= len2; j++) {
    dp[0][j] = j;
  }

  for (let i: number = 1; i <= len1; i++) {
    for (let j: number = 1; j <= len2; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
      }
    }
  }
  return dp[len1][len2];
}

go 解法

func minDistance(word1 string, word2 string) int {
    len1 := len(word1)
    len2 := len(word2)
    // dp表示长度为i的字符转换成长度为j的字符，需要的最少操作数
    dp := make([][]int, len1 + 1)
    // 初始化dp数组
    for i := 0; i <= len1; i ++ {
        dp[i] = make([]int, len2 + 1)
        dp[i][0] = i
    }
    for j := 0; j <= len2; j ++ {
        dp[0][j] = j
    }
    // 确定遍历方向
    for i := 1; i <= len1; i ++ {
        for j := 1; j <= len2; j ++ {
            // 确定转换方程,如果字符相同，则操作数不变。
            // 若不同，则取插入&删除&替换三种操作中最小的操作数+1
            if word1[i - 1] == word2[j - 1] {
                dp[i][j] = dp[i - 1][j - 1]
            } else {
                dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1
            }
        }
    }
    return dp[len1][len2]
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}