LeetCode 72. 编辑距离

Categories:

Tags:

题目描述
思路分析
1. 解法一：动态规划（双序列 DP）（推荐）
相似题目

题目描述

✅ 72. 编辑距离

题目：

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

允许对单词进行以下三种操作：插入一个字符、删除一个字符、替换一个字符。

示例 1：

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

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5

提示：

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

思路分析

解法一：动态规划（双序列 DP）（推荐）

核心思路：

定义 dp[i][j] 为将 word1[0..i-1] 转换为 word2[0..j-1] 所需的最少操作数。

边界初始化：

dp[i][0] = i：word1 前 i 个字符全部删除，需 i 次删除操作

dp[0][j] = j：word1 为空，需插入 j 个字符变成 word2，需 j 次插入操作

状态转移（i, j 从 1 开始）：

若 word1[i-1] == word2[j-1]：字符相同，无需操作： dp[i][j] = dp[i-1][j-1]

否则，取三种操作的最小值 + 1： dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1

dp[i][j-1] + 1：插入 word2[j-1] 到 word1 末尾

dp[i-1][j] + 1：删除 word1[i-1]

dp[i-1][j-1] + 1：替换 word1[i-1] 为 word2[j-1]

记忆口诀：左=插入，上=删除，左上=替换（以 dp 表格中方向理解）。

举例：word1 = "horse", word2 = "ros"，答案 dp[5][3] = 3：horse → rorse（替换 h→r）→ rose（删除 r）→ ros（删除 e）✓

复杂度分析：

时间复杂度：O(m × n)，其中 m、n 分别为 word1、word2 的长度，需填充整张 dp 表

空间复杂度：O(m × n)，其中 m、n 分别为两个字符串的长度，用于存储 dp 数组

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        // 边界初始化：word1 前 i 个字符全部删除
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        // 边界初始化：word1 为空时需插入 j 个字符
        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++) {
                // 字符相同，无需操作
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 取插入、删除、替换三种操作的最小值
                    dp[i][j] = Math.min(
                        dp[i - 1][j - 1],
                        Math.min(dp[i - 1][j], dp[i][j - 1])
                    ) + 1;
                }
            }
        }
        return dp[m][n];
    }
}

func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    // 边界初始化：word1 前 i 个字符全部删除
    for i := 0; i <= m; i++ {
        dp[i][0] = i
    }
    // 边界初始化：word1 为空时需插入 j 个字符
    for j := 0; j <= n; j++ {
        dp[0][j] = j
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            // 字符相同，无需操作
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                // 取插入、删除、替换三种操作的最小值
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
            }
        }
    }

    return dp[m][n]
}

相似题目

题目	难度	考察点
161. 相隔为 1 的编辑距离	中等	字符串 DP
583. 两个字符串的删除操作	中等	双序列 DP
712. 两个字符串的最小ASCII删除和	中等	双序列 DP
1035. 不相交的线	中等	双序列 DP（本质 LCS）
1143. 最长公共子序列	中等	双序列 DP
115. 不同的子序列	困难	二维 DP 子序列计数
10. 正则表达式匹配	困难	二维 DP 字符串匹配
97. 交错字符串	中等	二维 DP 字符串匹配

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/85653498