当前位置：首页 > article >正文

LeetCode 72 - 编辑距离 (Edit Distance)

article 2025/3/3 16:56:12

LeetCode 72 - 编辑距离 (Edit Distance) 是经典的动态规划问题，重点在于掌握基本的二维动态规划算法，理解动态规划的状态定义与转移，同时还能扩展到许多字符串匹配变体问题。这道题在算法和面试中的重要性极高，以下是解法及相关变体总结。

题目描述

输入：两个字符串 word1 和 word2。
要求：计算将 word1 转化为 word2 所需的最少操作数。
操作包括：
1. 插入一个字符。
2. 删除一个字符。
3. 替换一个字符。

示例

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

解法及分析

方法 1：二维动态规划（DP 表格法）

思路

定义状态：
- dp[i][j] 表示将 word1[0..i-1] 转换为 word2[0..j-1] 的最小编辑距离。
- 下标 i 和 j 表示字符串当前考虑的前缀长度。
状态转移方程：
- 如果 word1[i-1] == word2[j-1]：
```
dp[i][j] = dp[i-1][j-1]  // 两字符匹配，无需额外操作
```
- 如果 word1[i-1] != word2[j-1]，则尝试三种操作来转换：
  1. 插入：dp[i][j-1] + 1 —— 插入一个字符使两字符串对齐。
  2. 删除：dp[i-1][j] + 1 —— 删除当前字符。
  3. 替换：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[0][j] = j （将空字符串变为 word2，需要插入 j 个字符）。
- dp[i][0] = i （将 word1 转为空字符串，需删除 i 个字符）。

代码模板

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        // 初始化边界
        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++) {
                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]; // 返回最终结果
    }
}

复杂度分析

时间复杂度：O(m * n)，其中 m 和 n 是两个字符串的长度。
空间复杂度：O(m * n)，用于存储 dp 表。

方法 2：滚动数组优化空间（1D 优化）

核心思想

由于 dp[i][j] 的计算只依赖于当前行和上一行，因此可以用两个一维数组滚动更新，优化空间复杂度到 O(n)。

代码模板

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[] prev = new int[n + 1], curr = new int[n + 1];
        // 初始化第一行
        for (int j = 0; j <= n; j++) prev[j] = j;
        // 动态规划只用当前行和上一行
        for (int i = 1; i <= m; 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] = Math.min(prev[j - 1], 
                                Math.min(curr[j - 1], prev[j])) + 1;
                }
            }
            // 滚动数组
            int[] temp = prev;
            prev = curr;
            curr = temp;
        }
        return prev[n];
    }
}

复杂度分析

时间复杂度：O(m * n)，与上一方法相同。
空间复杂度：O(n)，只需两个一维数组。

方法 3：递归 + 记忆化搜索（自顶向下）

核心思想

将问题分解为子问题，并对重复子问题的解做缓存。

递归定义：

如果字符相等：dfs(word1, i, word2, j) = dfs(word1, i-1, word2, j-1)

如果字符不等：取三种操作的最小值：

dfs(word1, i, word2, j) = min(
    dfs(word1, i-1, word2, j-1) + 1, // 替换
    dfs(word1, i-1, word2, j) + 1,   // 删除
    dfs(word1, i, word2, j-1) + 1    // 插入
)

代码模板

class Solution {
    public int minDistance(String word1, String word2) {
        int[][] memo = new int[word1.length()][word2.length()];
        for (int[] row : memo) Arrays.fill(row, -1);
        return dfs(word1, word1.length() - 1, word2, word2.length() - 1, memo);
    }

    private int dfs(String word1, int i, String word2, int j, int[][] memo) {
        if (i < 0) return j + 1; // word1 空，返回插入操作数
        if (j < 0) return i + 1; // word2 空，返回删除操作数
        if (memo[i][j] >= 0) return memo[i][j]; // 缓存子问题解
        if (word1.charAt(i) == word2.charAt(j)) { // 字符匹配
            memo[i][j] = dfs(word1, i - 1, word2, j - 1, memo);
        } else { // 字符不同
            memo[i][j] = Math.min(dfs(word1, i - 1, word2, j - 1, memo), 
                            Math.min(dfs(word1, i - 1, word2, j, memo), 
                                     dfs(word1, i, word2, j - 1, memo)))
                         + 1;
        }
        return memo[i][j];
    }
}

复杂度分析

时间复杂度：O(m * n)，每个 (i, j) 状态只计算一次。
空间复杂度：O(m * n)，用于记忆化数组。

经典变体问题

变体 1：只允许插入/删除操作
- 假设 word1 转换到 word2 仅允许插入和删除字符。
- 思路：编辑距离简化为 LCS (最长公共子序列) 问题。
变体 2：变为回文的最小编辑距离
- 给定字符串 s，求变为回文的最少编辑距离。
- 思路：将问题转化为 s 和 reverse(s) 的编辑距离问题。
变体 3：匹配相似度问题
- 计算两个字符串的相似性。例如转换两字符串的最少操作数是否小于等于 k。
变体 4：带代价的编辑距离
- 插入、删除、替换不同操作有不同代价时，求最小编辑距离。
- 修改状态转移关系即可。