LeetCode72-编辑距离(EditDistance)

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

---

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

示例

输入: 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]，则尝试三种操作来转换： 插入：dp[i][j-1] + 1 —— 插入一个字符使两字符串对齐。删除：dp[i-1][j] + 1 —— 删除当前字符。替换：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：带代价的编辑距离

插入、删除、替换不同操作有不同代价时，求最小编辑距离。修改状态转移关系即可。

---

快速 AC 总结 直接背二维动态规划模板。练习滚动数组优化和记忆化搜素，注意空间优化。掌握变体问题（LCS、回文问题）并灵活转化。思路转化为代码时，优先理清边界初始条件。