HHot 100C++ 图解

72. 编辑距离

中等 多维动态规划 3 帧动画 在力扣上做

一句话套路替换/删除/插入三格取最小 +1

题目描述

给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数  。

你可以对一个单词进行如下三种操作:

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

 

示例 1:

输入:word1 = "horse", word2 = "ros"
输出:3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:

输入:word1 = "intention", word2 = "execution"
输出:5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

 

提示:

  • 0 <= word1.length, word2.length <= 500
  • word1 和 word2 由小写英文字母组成

思路

时间O(mn)
空间O(mn)

状态

dp[i][j] = word1 前 i 个变成 word2 前 j 个的最少操作数。

转移

字符相同 -> 直接继承对角线 dp[i-1][j-1](不需要操作);

不同 -> 三种操作取最小 +1:dp[i-1][j-1] + 1 替换dp[i-1][j] + 1 删除 word1 的最后一个dp[i][j-1] + 1 插入(等价于删 word2 的一个)

边界

dp[i][0] = i(全删)、dp[0][j] = j(全插)。这一行最容易忘。

家族

Q10 正则匹配、Q97 交错字符串、Q583 只能删除(= LCS 的变体)。

图解

i 0 n 1 t 2 e 3 n 4 t 5 i 6 o 7 n 8
字符串 intention(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/16_dp_multidim.cpp36 行
namespace lc0072 {
class Solution {
 public:
  int minDistance(const string& a, const string& b) {
    const int m = (int)a.size(), n = (int)b.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 0; i <= m; ++i) dp[i][0] = i;
    for (int j = 0; j <= n; ++j) dp[0][j] = j;
    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++j)
        dp[i][j] = (a[i - 1] == b[j - 1])
                       ? dp[i - 1][j - 1]
                       : 1 + min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]});
    return dp[m][n];
  }

  // 一维滚动版:注意 prev 保存的是「上一行左上角」的旧值
  static int minDistanceRolling(const string& a, const string& b) {
    const int m = (int)a.size(), n = (int)b.size();
    vector<int> dp(n + 1);
    for (int j = 0; j <= n; ++j) dp[j] = j;
    for (int i = 1; i <= m; ++i) {
      int diag = dp[0];  // dp[i-1][j-1]
      dp[0] = i;
      for (int j = 1; j <= n; ++j) {
        int old = dp[j];  // 这就是下一轮的 dp[i-1][j-1]
        dp[j] = (a[i - 1] == b[j - 1])
                    ? diag
                    : 1 + min({diag, dp[j], dp[j - 1]});  // 替换 / 删 / 插
        diag = old;
      }
    }
    return dp[n];
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q72_edit_distance17 行
lc0072::Solution s;
CHECK_EQ(s.minDistance("horse", "ros"), 3);
CHECK_EQ(s.minDistanceRolling("horse", "ros"), 3);
CHECK_EQ(s.minDistance("intention", "execution"), 5);
CHECK_EQ(s.minDistanceRolling("intention", "execution"), 5);
CHECK_EQ(s.minDistance("", "abc"), 3);
CHECK_EQ(s.minDistance("abc", ""), 3);
CHECK_EQ(s.minDistance("", ""), 0);
CHECK_EQ(s.minDistance("abc", "abc"), 0);
CHECK_EQ(s.minDistance("ab", "ba"), 2);
CHECK_EQ(s.minDistance("foo", "bar"), 3);  // 三位全替换
CHECK_EQ(s.minDistance("abb", "a"), 2);    // 删两个
// 二维版与一维滚动版必须在任意输入上一致(互相检验实现正确性)
vector<pair<string, string>> cases{{"horse", "ros"}, {"abcab", "cba"},  {"", "aaaa"},
                                    {"a", "pqrs"},   {"intention", "execution"}, {"ab", "ba"}};
for (const auto& c : cases) CHECK_EQ(s.minDistance(c.first, c.second),
                                     s.minDistanceRolling(c.first, c.second));

↑↓ 选择↵ 打开/ 随时唤起