代码随想录动态规划——编辑距离

题目

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

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

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

示例 1： 输入：word1 = “horse”, word2 = “ros” 输出：3
解释：horse -> rorse (将 ‘h’ 替换为 ‘r’) rorse -> rose (删除 ‘r’) rose -> ros (删除 ‘e’)

示例 2： 输入：word1 = “intention”, word2 = “execution” 输出：5 解释： intention-> inention (删除 ‘t’) inention -> enention (将 ‘i’ 替换为 ‘e’) enention -> exention (将 ‘n’ 替换为 ‘x’) exention -> exection (将 ‘n’ 替换为 ‘c’) exection -> execution (插入 ‘u’)

提示：

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

思路

编辑距离是用dp解决的经典题目

动规五部曲：

1. 确定dp数组及下标含义
   dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]，这里是方便后序操作，比如以下标i-2为结尾的word1 与 j-2为结尾的word2的最近编辑距离就是dp[i-1[j-1]
2. 确定递推公式
   一共分成四种情况

if (word1[i - 1] == word2[j - 1])
    不操作
if (word1[i - 1] != word2[j - 1])
    1、增加
    2、删除
    3、替换
1
2
3
4
5
6

当word1[i - 1] == word2[j - 1]时
（1）不操作：dp[i][j] = dp[i - 1][j - 1]

当word1[i - 1] ！= word2[j - 1]时
（2）word1删除一个元素，那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作，即dp[i][j] = dp[i - 1][j] + 1
（3）word2删除一个元素，那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作，即dp[i][j] = dp[i][j - 1] + 1

注意：word2添加一个元素，相当于word1删除一个元素，例如 word1 = “ad” ，word2 = “a”，word1删除元素’d’ 和 word2添加一个元素’d’，变成word1=“a”, word2=“ad”， 最终的操作数是一样

（4）word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增加元素，那么以下标i-2为结尾的word1 与 j-2为结尾的word2的最近编辑距离 加上一个替换元素的操作，即dp[i][j] = dp[i - 1][j - 1] + 1
最后取最小值，即dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1

3. dp数组初始化
   dp[i][0] ：以下标i-1为结尾的字符串word1，和空字符串word2的最近编辑距离，要得到空字符串，那么dp[i][0]就应该是i，对word1里的元素全部做删除操作，即：dp[i][0] = i；同理dp[0][j] = j

4. 确定遍历顺序
   一共四个递推公式

dp[i][j] = dp[i - 1][j - 1]
dp[i][j] = dp[i - 1][j - 1] + 1
dp[i][j] = dp[i][j - 1] + 1
dp[i][j] = dp[i - 1][j] + 1
1
2
3
4

在dp矩阵中一定是从左到右从上到下去遍历

5. 举例推导dp数组
   以示例1为例，输入：word1 = “horse”, word2 = "ros"为例，dp矩阵状态图如下：
   

java代码如下：

class Solution {
	public int minDistance(String word1, String word2){
		int m = word1.length();
		int 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++){
			   	// 因为dp数组有效位从1开始,所以申请的是1~m,1~n,即dp[m+1][n+1]
            	// 所以当前遍历到的字符串的位置为i-1 | j-1
				if(word1.charAt(i-1) == word2.charAt(j-1)){
					dp[i][j] = dp[i-1][j-1];
				} else {
					dp[i][j] = Math.min(Math.min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1]) + 1;//因为min()只有两个参数
				}
			}
		}
		return dp[m][n];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26