LeetCode 72. 编辑距离

约 5 分钟
文章信息 28 个分类 4 个标签
分类
LeetCode CodeTop 中等 已解决 未掌握 200-500 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 京东 华为 拼多多 网易 小米 商汤 虾皮 携程 哔哩哔哩 小红书 LeetCode 75 LeetCode 热题 100 面试经典 150 题
标签
字符串 动态规划 动态规划经典题 子序列问题
目录

题目描述

✅ 72. 编辑距离

image-20230307190443960

image-20230307190448358

题意分析

输入两个字符串 word1 和 word2，允许的操作只有三种：在任意位置插入一个字符、删除一个字符、把某个字符替换成另一个字符。要求返回把 word1 变成 word2 所需的最少操作次数。

题目只要一个数值，不要求输出具体的操作序列，这意味着不需要记录路径，只要能把「最少次数」递推出来即可。操作允许发生在任意位置，而不是只能在末尾，这个自由度是题意里最容易被低估的一点。

三种操作是成对对称的：在 word1 里插入一个字符，等价于在 word2 里删除一个字符；替换则是唯一一个同时消耗两串各一个字符的操作。所以整个问题本质上是把两个串「对齐」，未被对齐的字符各自付一次代价。

需要单独想清楚的边界有四类：word1 为空时答案是 word2 的长度；word2 为空时答案是 word1 的长度；两串完全相同时答案是 0；两串没有任何公共字符时答案是较长串的长度（重叠部分逐位替换，多出来的部分插入或删除）。

解法：滚动数组动态规划

核心思路

定义 dp[j] 为当前已处理的 word1 前缀转换成 word2 前 j 个字符的最少操作数。逐行更新时，dp[j] 的旧值是上方状态，dp[j - 1] 是左侧状态，变量 pre 保存左上角状态。字符相同则继承左上角，否则在替换、删除、插入三种操作中取最小值并加一。

解题步骤

  • 将较短字符串放在内层，使滚动数组长度最小。
  • 初始化 dp[j] = j，表示空串变成长度为 j 的前缀需要插入 j 次。
  • 每行先保存旧的 dp[0] 到 pre，再令 dp[0] = i。
  • 字符相同则令 dp[j] = pre；否则取左上、上方、左侧三个状态的最小值并加一。
  • 更新 pre 前先保存 dp[j] 的旧值，最后返回 dp[n]。

代码实现

class Solution {
    public int minDistance(String word1, String word2) {
        if (word1.length() < word2.length()) {
            String temp = word1;
            word1 = word2;
            word2 = temp;
        }

        int[] dp = new int[word2.length() + 1];
        for (int j = 0; j < dp.length; j++) {
            dp[j] = j;
        }

        for (int i = 1; i <= word1.length(); i++) {
            int pre = dp[0];
            dp[0] = i;

            for (int j = 1; j <= word2.length(); j++) {
                int up = dp[j];
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[j] = pre;
                } else {
                    dp[j] = Math.min(pre, Math.min(up, dp[j - 1])) + 1;
                }
                pre = up;
            }
        }

        return dp[word2.length()];
    }
}

func minDistance(word1 string, word2 string) int {
    if len(word1) < len(word2) {
        word1, word2 = word2, word1
    }

    dp := make([]int, len(word2)+1)
    for j := range dp {
        dp[j] = j
    }

    for i := 1; i <= len(word1); i++ {
        pre := dp[0]
        dp[0] = i

        for j := 1; j <= len(word2); j++ {
            up := dp[j]
            if word1[i-1] == word2[j-1] {
                dp[j] = pre
            } else {
                dp[j] = minInt(pre, minInt(up, dp[j-1])) + 1
            }
            pre = up
        }
    }

    return dp[len(word2)]
}

func minInt(a int, b int) int {
    if a < b {
        return a
    }
    return b
}

复杂度分析

  • 时间复杂度：$O(mn)$，每个前缀组合计算一次。
  • 空间复杂度：$O(\min(m, n))$，滚动数组按较短字符串分配。

关键点总结

  • 三个转移来源分别对应替换、删除和插入。
  • pre 必须保存覆盖前的左上角状态，dp[j] 更新后再令 pre = up。
  • 第一行和第一列表示空前缀，是动态规划的边界。

易错点总结

  • dp[0] 每行都要更新为 i，否则空串边界错误。
  • 字符下标是前缀长度减一，即 i - 1 和 j - 1。
  • 更新 pre 前必须先保存旧的 dp[j]，否则左上角状态会丢失。
  • 字符相同时不增加操作次数。

相似题目

题目 难度 考察点
97. 交错字符串 中等 状态含义从「最少代价」变成「可行性」，转移取或而不是取最小值
583. 两个字符串的删除操作 中等 去掉替换操作，只剩插入删除，答案等价于两串长度和减去两倍 LCS
712. 两个字符串的最小ASCII删除和 中等 每次删除的代价不再是 1，而是字符的 ASCII 值，转移里加的是权重
1035. 不相交的线 中等 几何连线问题剥掉外壳后就是求最大匹配数，取最大值而不是最小代价
1143. 最长公共子序列 中等 同一张表求最大保留长度，字符不同时不付代价而是直接丢弃一侧
LCR 095. 最长公共子序列 中等 与 1143 同题，可用来对照「取最小代价」和「取最大长度」两种转移的写法差异
LCR 096. 交错字符串 中等 与 97 同题，第三个串的下标由前两个下标之和唯一确定，状态维度反而更少