两个字符串的删除操作

583. 两个字符串的删除操作

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] + 2)。相当于删除 word1[i - 1] 或者 word2[j - 1]，或者两个都删除。

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

typescript 解法

function minDistance(word1: string, word2: string): number {
  const length1: number = word1.length;
  const length2: number = word2.length;
  const dp: number[][] = new Array(length1 + 1)
    .fill(0)
    .map(() => new Array(length2 + 1).fill(0));
  for (let i: number = 0; i <= length1; i++) {
    dp[i][0] = i;
  }
  for (let j: number = 0; j <= length2; j++) {
    dp[0][j] = j;
  }
  for (let i: number = 1; i <= length1; i++) {
    for (let j: number = 1; j <= length2; 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] + 1,
          dp[i][j - 1] + 1,
          dp[i - 1][j - 1] + 2
        );
      }
    }
  }
  return dp[length1][length2];
}

go 解法

func minDistance(word1 string, word2 string) int {
    // dp 表示下标为i的word1转换成下表为j的word2需要的最小步数。
    len1 := len(word1)
    len2 := len(word2)
    // 初始化dp数组
    dp := make([][]int, len1 + 1)
    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 ++ {
            // 确定转移方程：当word1[i - 1] == word2[j - 1]时，dp[i][j] = dp[i - 1][j - 1]
            // 不相等时，dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 2)
            // 相当于删除word1[i - 1]或者word2[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]) + 1, dp[i - 1][j - 1] + 2)
            }
        }
    }
    return dp[len1][len2]
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}