72. 编辑距离#

大家好！今天我们要深入探讨一个在自然语言处理、DNA序列比较和拼写检查等领域广泛应用的经典问题——编辑距离(Edit Distance)。这也是动态规划的一个精彩应用，让我们一起揭开它的奥秘！

🌟 编辑距离：衡量字符串相似度的标准#

编辑距离，也被称为Levenshtein距离，是用来量化两个字符串之间差异的一种度量。它代表将一个字符串转换成另一个字符串所需的最少单字符编辑操作次数。

编辑操作通常包括三种：

插入：在字符串中插入一个字符
删除：从字符串中删除一个字符
替换：将字符串中的一个字符替换为另一个字符

这个概念看似简单，却能精确地反映出两个字符串的结构相似程度！

问题描述#

题目目标#

给你两个单词 word1 和 word2 ，请返回将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行插入、删除或替换一个字符三种操作。

示例 1#

输入： word1 = "horse", word2 = "ros" 输出： 3 说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

🎯 问题描述：字符串转换的最优路径#

给定两个单词word1和word2，计算将word1转换成word2所使用的最少操作数。

例如：

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

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

plaintext

🤔 从小例子开始思考#

让我们通过一个简单例子来理解这个问题：

word1 = "cat"
word2 = "bat"

plaintext

我们需要找出将”cat”转换为”bat”的最少操作次数。很明显，我们只需要一步：将’c’替换为’b’，所以编辑距离为1。

再看一个稍复杂的例子：

word1 = "sunday"
word2 = "saturday"

plaintext

一种可能的转换路径是：

sunday -> surday (将’n’替换为’r’)
surday -> saturday (插入’at’)

所以编辑距离为3。但这是最优解吗？我们需要一个系统的方法来确定最少操作数。

💡 递归思路：自顶向下的分解#

考虑两个字符串的最后一个字符：

如果它们相等，那么问题缩小为求解两个字符串分别去掉最后一个字符后的编辑距离。
如果它们不相等，我们有三种操作选择：
- 替换：word1的最后一个字符替换为word2的最后一个字符，然后问题缩小为求解两个字符串分别去掉最后一个字符后的编辑距离。
- 插入：在word1末尾插入word2的最后一个字符，这样问题缩小为word1和word2去掉最后一个字符后的编辑距离。
- 删除：删除word1的最后一个字符，问题缩小为去掉最后一个字符的word1和完整的word2的编辑距离。

我们取这三种操作中的最小值，再加上当前的操作次数1。

用递归表达：

EditDistance(i, j) = 表示word1[0...i]变换到word2[0...j]的最少操作次数

如果word1[i] == word2[j]:
    EditDistance(i, j) = EditDistance(i-1, j-1)
否则:
    EditDistance(i, j) = 1 + min(
        EditDistance(i-1, j-1),  // 替换
        EditDistance(i, j-1),    // 插入
        EditDistance(i-1, j)     // 删除
    )

plaintext

📝 动态规划解法：自底向上的构建#

递归会导致大量重复计算，我们使用动态规划来优化：

class Solution {
    public int minDistance(String word1, String word2) {
        // m 表示 word1 的长度
        int m = word1.length();
        // n 表示 word2 的长度
        int n = word2.length();

        // dp[i][j] 表示：把 word1 的前 i 个字符转换为 word2 的前 j 个字符的最少操作数
        int[][] dp = new int[m+1][n+1];

        // 初始化第 0 列：把 word1 前 i 个字符变成空串，只能做 i 次删除
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }

        // 初始化第 0 行：把空串变成 word2 前 j 个字符，只能做 j 次插入
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        // 从长度为 1 的前缀开始，逐步填充整个 dp 表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 若当前末尾字符相同，则无需额外操作，沿用左上角状态
                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    // 否则三种操作取最小值再 +1：
                    // 1) 替换：dp[i-1][j-1]
                    // 2) 插入：dp[i][j-1]
                    // 3) 删除：dp[i-1][j]
                    dp[i][j] = 1 + Math.min(dp[i-1][j-1],  // 替换
                                  Math.min(dp[i][j-1],     // 插入
                                           dp[i-1][j]));   // 删除
                }
            }
        }

        // 右下角即把整个 word1 转成整个 word2 的最少操作数
        return dp[m][n];
    }
}

java

时间复杂度：O(m×n)，其中m和n分别是两个字符串的长度空间复杂度：O(m×n)，需要一个二维数组存储中间结果

🎨 图解动态规划：可视化理解过程#

以word1 = “horse”, word2 = “ros”为例，让我们看看dp数组的填充过程：

   |   | r | o | s
---+---+---+---+---
   | 0 | 1 | 2 | 3
---+---+---+---+---
 h | 1 | 1 | 2 | 3
---+---+---+---+---
 o | 2 | 2 | 1 | 2
---+---+---+---+---
 r | 3 | 2 | 2 | 2
---+---+---+---+---
 s | 4 | 3 | 3 | 2
---+---+---+---+---
 e | 5 | 4 | 4 | 3

plaintext

例如，当我们计算dp[2][2]时，表示”ho”和”ro”的编辑距离：

word1[2-1] = ‘o’，word2[2-1] = ‘o’，它们相等
所以dp[2][2] = dp[1][1] = 1
意味着”ho”变成”ro”的最少操作数为1（仅需将’h’替换为’r’）

最终dp[5][3] = 3，表示”horse”变成”ros”的编辑距离为3。

💫 空间优化：滚动数组#

由于dp[i][j]只依赖于当前行和前一行的值，我们可以使用两个一维数组或者滚动一维数组来优化空间：

class Solution {
    public int minDistance(String word1, String word2) {
        // m、n 分别是两个字符串长度
        int m = word1.length();
        int n = word2.length();

        // 让 word1 尽量短（通过交换参数），便于后续空间优化
        if (m > n) {
            return minDistance(word2, word1);
        }

        // prev 表示上一行（i-1），curr 表示当前行（i）
        int[] prev = new int[n+1];
        int[] curr = new int[n+1];

        // 初始化第 0 行：空串到 word2 前 j 个字符需要 j 次插入
        for (int j = 0; j <= n; j++) {
            prev[j] = j;
        }

        // 逐行计算 dp
        for (int i = 1; i <= m; i++) {
            // 当前行第 0 列：word1 前 i 个字符到空串，需要 i 次删除
            curr[0] = i;

            for (int j = 1; j <= n; j++) {
                // 当前字符相同，不需要新增操作
                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    curr[j] = prev[j-1];
                } else {
                    // 当前字符不同，从替换/插入/删除三种操作中取最优
                    curr[j] = 1 + Math.min(prev[j-1],  // 替换
                                 Math.min(curr[j-1],   // 插入
                                           prev[j]));   // 删除
                }
            }

            // 本行计算完后交换引用：下一轮把 curr 当作上一行使用
            int[] temp = prev;
            prev = curr;
            curr = temp;
        }

        // 最终答案位于“最后一行”的末尾，即 prev[n]
        return prev[n];
    }
}

java

进一步优化，我们可以只用一个一维数组：

class Solution {
    public int minDistance(String word1, String word2) {
        // m、n 分别是两个字符串长度
        int m = word1.length();
        int n = word2.length();

        // 一维 dp：dp[j] 表示当前处理到 word1 前缀时，转换到 word2 前 j 个字符的最小操作数
        int[] dp = new int[n+1];

        // 初始化第 0 行：空串转换到 word2 前 j 个字符需要 j 次插入
        for (int j = 0; j <= n; j++) {
            dp[j] = j;
        }

        // 外层遍历 word1 前缀长度 i
        for (int i = 1; i <= m; i++) {
            // prev 保存“左上角旧值”dp[i-1][j-1]，初始对应 j=0 时的 dp[i-1][0]
            int prev = dp[0];
            // 更新当前行第 0 列：word1 前 i 个字符到空串需要 i 次删除
            dp[0] = i;

            for (int j = 1; j <= n; j++) {
                // temp 暂存更新前的 dp[j]，它是下一列要用的“左上角旧值”
                int temp = dp[j];

                // 若当前字符相同，不需要新增操作，直接继承左上角
                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[j] = prev;
                } else {
                    // 若不同，则在替换/插入/删除三者中选最小并 +1
                    dp[j] = 1 + Math.min(prev,      // 替换
                                 Math.min(dp[j-1],   // 插入
                                          dp[j]));   // 删除
                }

                // 把左上角旧值推进到下一列
                prev = temp;
            }
        }

        // dp[n] 即最终编辑距离
        return dp[n];
    }
}

java

时间复杂度：O(m×n) 空间复杂度：O(min(m,n))，只需要一个长度为较短字符串长度的数组

🔄 编辑距离与LCS的关系#

编辑距离与最长公共子序列(LCS)有着密切的关系。实际上，对于仅允许插入和删除（不允许替换）的情况，编辑距离与LCS之间存在这样的关系：

编辑距离 = 字符串1长度 + 字符串2长度 - 2×LCS长度

plaintext

这个公式揭示了两个问题的本质联系：LCS寻找的是需要保留的部分，而编辑距离关注的是需要修改的部分。同一个问题，两种视角！

🔀 编辑距离的变体问题#

编辑距离有许多有趣的变体：

带权重的编辑距离：不同操作有不同的成本
最长公共子序列：可以视为特殊的编辑距离问题
最短公共超序列：构造包含两个字符串的最短序列
模糊字符串匹配：允许一定编辑距离内的匹配

🌐 现实应用：从拼写检查到基因序列比较#

编辑距离在实际中有众多应用：

拼写检查：找出与错误单词编辑距离最小的正确单词
语音识别：比较识别结果与候选词的相似度
生物信息学：比较DNA或蛋白质序列的相似性
抄袭检测：评估文档之间的相似程度
机器翻译：评估翻译质量

💯 编辑距离的本质：寻找最优变换路径#

从算法的本质看，编辑距离是在寻找字符串间转换的”最短路径”。这种思想在计算机科学的许多领域都有体现：

图论：寻找图中两点之间的最短路径
状态转换：在状态空间中找到最优转换序列
序列对齐：找到两个序列的最佳对齐方式

🎓 面试技巧与常见陷阱#

面试中关于编辑距离的常见问题：

初始化问题：dp数组的基础情况需要正确初始化，表示空字符串与另一字符串的编辑距离
操作定义：明确插入、删除和替换的具体定义和方向
空间优化：如何从O(m×n)优化到O(min(m,n))
回溯构建：如何回溯得到实际的编辑操作序列

💡 解题思路总结#

解决编辑距离问题的关键步骤：

理解问题：明确三种编辑操作的定义
定义状态：dp[i][j]表示将word1的前i个字符转换为word2的前j个字符的最少操作数
找出转移方程：当字符相等/不相等时如何转移
确定边界条件：空字符串转换的情况
空间优化：从二维到一维的转变
实际应用：如何应用于实际问题

🤔 思考题#

如果编辑操作的成本不同（例如，插入成本为1，删除成本为2，替换成本为3），动态规划的状态转移方程会如何变化？如何修改我们的算法来处理这种带权重的编辑距离？

编辑距离是理解动态规划思想的又一个绝佳例子，它展示了如何通过分解问题并建立最优子结构来高效求解。掌握编辑距离，不仅能帮助我们解决算法题，更能应用于日常开发中的文本处理、相似度匹配等实际问题！

🌉 编辑距离与其他算法的联系#

编辑距离是连接多种算法思想的桥梁，它与最长公共子序列、序列对齐、字符串匹配等问题紧密相连。理解编辑距离，就像掌握了处理字符串相似度问题的通用框架。

从更广泛的角度看，编辑距离是一种衡量”差异”的方式，而这种”差异度量”的思想在数据挖掘、模式识别、信息检索等领域都有深远应用。当我们能够量化差异，就能找到将差异最小化的路径——这正是优化问题的核心！

在未来的算法学习中，建立这种问题之间的联系将帮助我们构建更加系统化的算法知识网络，而不仅仅是孤立地解决单个问题。