如何计算两个字符串的编辑距离？

核心回答

通常按 Levenshtein 编辑距离回答：允许插入、删除、替换一个字符，每次成本为 1，求把一个字符串变成另一个的最少次数。它不包含“交换相邻字符算一次”这种额外操作。

用动态规划，定义 dp[i][j] 为把 word1 前 i 个字符变成 word2 前 j 个字符的最小成本。两个末尾字符相同，就沿用左上角；不同，就从删除、插入和替换三种选择中取最小成本，再加 1。空串对应首行和首列，分别初始化为目标或源前缀的长度。

完整表需要 O(mn) 时间和空间。只求距离时，每个状态只依赖上一行和当前行前一项，可以滚动保存两行，把额外空间降到 O(min(m, n) + 1)。

状态和三种转移怎样对应

先把问题固定为“将 word1 转成 word2”，就不容易把操作方向说反。

• 末尾相同： dp[i][j] = dp[i - 1][j - 1]，这两个字符可以直接匹配。
• 删除源串末尾： 从 dp[i - 1][j] 转移，成本加 1。
• 插入目标串末尾： 先把源前缀变成目标的前 j − 1 个字符，再补最后一个，即 dp[i][j - 1] + 1。
• 替换源串末尾： 先匹配两边更短的前缀，再替换当前字符，即 dp[i - 1][j - 1] + 1。

末尾不同时，取后三项的最小值。二维状态按 i、j 递增计算，确保左边、上边和左上边都已求出。最后返回完整长度对应的 dp[m][n]，不是表中的全局最小值。

边界也来自状态定义：dp[0][j] = j 表示空串需要插入 j 次；dp[i][0] = i 表示删除 i 次；dp[0][0] = 0。

Python 实现：保留两行

下面把较短的字符串放在列方向。三种操作成本相同，距离具有对称性，因此交换两串不会改变答案。

def edit_distance(word1: str, word2: str) -> int:
    if len(word1) < len(word2):
        word1, word2 = word2, word1
    if not word2:
        return len(word1)

    previous = list(range(len(word2) + 1))
    for i, source_char in enumerate(word1, 1):
        current = [i]
        for j, target_char in enumerate(word2, 1):
            if source_char == target_char:
                current.append(previous[j - 1])
            else:
                current.append(
                    1 + min(previous[j], current[j - 1], previous[j - 1])
                )
        previous = current
    return previous[-1]

previous[j] 是上一行同列，current[j - 1] 是本行左侧，previous[j - 1] 是左上角。每一行都重新把第 0 列设为 i，避免把空目标串的边界丢掉。

每行完成后再替换 previous，仍然只同时保留两行。空串分支直接返回长度；两个非空字符串的时间复杂度为 O(mn)，额外空间为 O(min(m, n) + 1)。

例子怎样检查

把 cat 变成 cut，保留 c 和 t，将 a 替换成 u，距离是 1。把 cat 变成 at，删除 c，距离也是 1。

ab 变成 ba 的距离是 2，例如替换两个位置；本题没有一次交换操作。两个相同字符串距离为 0；空串变成 abc 的距离为 3。这些样例分别检查替换、删除、操作定义、相同字符和边界。

常见追问

只用一行还能算吗？

可以，但从左向右更新时，旧的左上角会被覆盖，需要额外变量保存。两行写法更容易说明每个值的来源，空间阶数相同。若改成倒序更新，又会缺少本行已经求出的左侧状态，不能直接照搬其他 DP 的倒序技巧。

要返回具体修改步骤怎么办？

可以保留完整 DP 表和转移选择，从右下角回溯。相同末尾走左上，删除走上方，插入走左方，替换走左上方。多个转移同样最优时，可以任选一条或定义稳定的优先级。当前滚动实现只返回距离，没有保留这条路径。

插入、删除、替换的代价不同呢？

把各转移的加 1 换成对应成本，首行首列也按各自成本累计。此时距离未必对称，不能直接交换两串来节省列空间；要同步调整方向和代价。若允许相邻交换，还需要相应的新状态转移，不能仅修改一个成本值。

参考资料