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

95.编辑距离

news 2026/3/26 22:06:24

72. 编辑距离

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

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

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

【思路】

定义状态：dp[i][j] 表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最少操作数。
初始化边界：
- 当 i=0（word1 为空），需要插入 j 个字符才能得到 word2 的前 j 个字符 → dp[0][j] = j；
- 当 j=0（word2 为空），需要删除 i 个字符才能得到空字符串 → dp[i][0] = i。
状态转移：
- 如果 word1[i-1] == word2[j-1]（当前字符相等），无需操作 → dp[i][j] = dp[i-1][j-1]；
- 如果 word1[i-1] != word2[j-1]（当前字符不等），取「替换、删除、插入」三种操作的最小值 + 1：
  - 替换：dp[i-1][j-1] + 1（把 word1 [i-1] 换成 word2 [j-1]）；
  - 删除：dp[i-1][j] + 1（删除 word1 [i-1]）；
  - 插入：dp[i][j-1] + 1（在 word1 末尾插入 word2 [j-1]）；
    
    → dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1。

【总结】

初始化：word1 为空插入dp[0][i] = i；word1 一个也对不上dp[i][0] = i 全删掉

word1[i] == word2[j] 保持不变，不用加次数

否则插入、删除、替换的最小值+1

注意min一次只能比较两个值，先比较两个再比较两个。

class Solution {public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();// 创建dp数组，dp[i][j]表示word1前i个字符转word2前j个字符的最少操作数int[][] dp = new int[m + 1][n + 1];// 初始化：word1为空，需要插入j个字符for (int j = 0; j <= n; j++)  dp[0][j] = j; // 初始化：word2为空，需要删除i个字符for (int i = 0; i <= m; i++)  dp[i][0] = i; // 填充dp数组for (int i = 1; i <= m; i++) {char c1 = word1.charAt(i - 1);for (int j = 1; j <= n; j++) {char c2 = word2.charAt(j - 1);if (c1 == c2) {// 字符相等，无需操作，继承上一个状态dp[i][j] = dp[i - 1][j - 1];} else {// 字符不等，取替换、删除、插入的最小值 + 1dp[i][j] = Math.min(Math.min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1]) + 1;}}}// dp[m][n]即为整个word1转word2的最少操作数return dp[m][n];}
}