72. 编辑距离——【Leetcode每日一题】

柔情只为你懂 2024-03-26 00:08 108阅读 0赞

### 72. 编辑距离 ###

给你两个单词 `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` 由小写英文字母组成

#### 思路：(动态规划) ####

1.  动态规划问题最重要的是先**确定一共有哪些状态**；
2.  然后分析每种状态的关系，从而确定 **状态转移方程**。

**第一步：确定所有的状态：**

我们随意看 `word1` 的第 `i` 个字符，和 `word2` 的第 `j` 个字符,这两个字符**可能相等**，**可能不相等**，即共有**两种状态**：

*  1、**相等**
 *  2、**不相等**

**第二步：分析每种状态的关系，确定状态转移方程：**

定义二维`dp`数组，`dp[i][j]` 表示为 `word1` 的前 `i` 个字符转换成 `word2` 的前 `j` 个字符所使用的最少操作数。

*  1、**相等**的情况下，求最少操作数，当相等的时候不进行任何操作的情况下最小，此时的操作数，等于 `word1` 的前 `i - 1` 个字符转换成 `word2` 的前 `j - 1` 个字符的操作数，即：  
     d p \[ i \] \[ j \] = d p \[ i − 1 \] \[ j − 1 \] dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\] dp\[i\]\[j\]=dp\[i−1\]\[j−1\]
 *  2、**不相等**的情况下，有三种操作：
    
     *  **替换** ：把 `word1` 的第 `i` 个字符，**替换**成 `word2` 的第 `j` 个字符，此时**总操作数**等于 `word1` 的前 `i - 1` 个字符转换成 `word2` 的前 `j - 1` 个字符的操作数 + 1，即：  
         d p \[ i \] \[ j \] = d p \[ i − 1 \] \[ j − 1 \] + 1 dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\] + 1 dp\[i\]\[j\]=dp\[i−1\]\[j−1\]\+1
     *  **插入：在 `word1` 的第 `i` 个字符后面，插入 `word2` 的第 `j` 个字符，此时总操作数**等于 `word1` 的前 `i` 个字符转换成 `word2` 的前 `j - 1` 个字符的操作数 + 1，即：  
         d p \[ i \] \[ j \] = d p \[ i \] \[ j − 1 \] + 1 dp\[i\]\[j\] = dp\[i\]\[j - 1\] + 1 dp\[i\]\[j\]=dp\[i\]\[j−1\]\+1
     *  **删除：** 删除`word1` 的第 `i` 个字符，此时**总操作数**等于 `word1` 的前 `i - 1` 个字符转换成 `word2` 的前 `j` 个字符的操作数 + 1，即：  
         d p \[ i \] \[ j \] = d p \[ i − 1 \] \[ j \] + 1 dp\[i\]\[j\] = dp\[i - 1\]\[j\] + 1 dp\[i\]\[j\]=dp\[i−1\]\[j\]\+1
     *  求最少操作数，即**不相等**的时候，取这三种操作的最小值，即不相等时，**总操作数**为：  
         d p \[ i \] \[ j \] = m i n ( d p \[ i − 1 \] \[ j − 1 \] , d p \[ i \] \[ j \] = d p \[ i \] \[ j − 1 \] , d p \[ i − 1 \] \[ j \] ) + 1 dp\[i\]\[j\] = min(dp\[i - 1\]\[j - 1\], dp\[i\]\[j\] = dp\[i\]\[j - 1\], dp\[i - 1\]\[j\] ) + 1 dp\[i\]\[j\]=min(dp\[i−1\]\[j−1\],dp\[i\]\[j\]=dp\[i\]\[j−1\],dp\[i−1\]\[j\])\+1

**第三步：定义边界初始状态：**

*  `word1`不为空，目标串`word2`长度为空，则需要**删除**，**总操作数**为`word1`的长度；
 *  `word1`为空，目标串`word2`长度不为空，则需要**插入**，**总操作数**为`word2`的长度；

**例如：**  
`word1 = "inten"`转换为 `word2 = "execu"` 的`dp`数组：

![在这里插入图片描述][e679a6842fc54c169de7f539ff0c7653.jpeg]

#### 代码：(Java) ####

public class MinDistance2 {
        
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		String word1 = "intention";
    		String word2 = "execution";
    		System.out.println(minDistance(word1, word2));
    	}
    	public static int minDistance(String word1, String word2) {
        
    		
    		int n = word1.length();
    		int m = word2.length();//目标单词
    		
    		int dp[][] = new int[m + 1][n + 1];
    		
    		//初始化
    		for(int i = 1; i <= n; i++) {
        
    			dp[0][i] = i;
    		}
    		for(int i = 1; i <= m; i++) {
        
    			dp[i][0] = i;
    		}
    
    		for(int i = 1; i <= m; i++) {
        
    			for(int j = 1; j <= n; j++) {
        
    				if(word1.charAt(j - 1) == word2.charAt(i - 1)) {
        
    					dp[i][j] = dp[i - 1][j - 1];
    				}else{
        //替换、插入、删除，取最小值
    					dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
    				}
    			}
    		}
    		return dp[m][n];
    	}
    }

##### 运行结果： #####

![在这里插入图片描述][6d344f226844461a80c443ec3d6b462f.png]

##### 复杂度分析： #####

*  **时间复杂度**： O ( n m ) O(nm) O(nm)，其中 `n` 为 `word1` 的长度，`m` 为 `word2` 的长度。
 *  **空间复杂度**： O ( n m ) O(nm) O(nm)，其中 `n` 为 `word1` 的长度，`m` 为 `word2` 的长度, 我们需要大小为  O ( n m ) O(nm) O(nm) 的 `dp` 数组来记录状态值。

##### 注：仅供学习参考， 如有不足，欢迎指正！ #####

题目来源：[力扣。][Link 1]

[e679a6842fc54c169de7f539ff0c7653.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/32a23634a0f245bf802b20bf84fe20a7.png
[6d344f226844461a80c443ec3d6b462f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/e335be6b70ca472d898f75387f728d4b.png
[Link 1]: https://leetcode.cn/problems/edit-distance/description/