给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

进阶：

  • 一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
  • 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
  • 你能想出一个仅使用常量空间的解决方案吗？

思路

  1. O(m + n) 是常规方案，极端情况下需要记录 m + n 个坐标
  2. 想要通过额外的常数空间解决问题，必须利用上现有的空间
  3. 借 matrix 中的一行一列可以达成目的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var minDistance = function (word1, word2) {
  const dp = new Array(word1.length + 1).fill(null).map(() => new Array(word2.length + 1).fill(0))
  for (let i = 0; i <= word1.length; ++i) {
    dp[i][0] = i
  }
  for (let j = 0; j <= word2.length; ++j) {
    dp[0][j] = j
  }
  for (let i = 0; i < word1.length; ++i) {
    for (let j = 0; j < word2.length; ++j) {
      if (word1[i] === word2[j]) {
        dp[i + 1][j + 1] = dp[i][j]
      } else {
        dp[i + 1][j + 1] = Math.min(dp[i + 1][j], dp[i][j + 1], dp[i][j]) + 1
      }
    }
  }
  return dp[word1.length][word2.length]
}