LeetCode-72. 编辑距离

红太狼 2024-03-24 12:49 41阅读 0赞

#### 目录 ####

*  动态规划

题目来源  
[72. 编辑距离][72.]

## 动态规划 ##

*  1.确定dp数组（dp table）以及下标的含义

dp\[i\]\[j\] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp\[i\]\[j\]。

*  2.确定递推公式

在确定递推公式的时候，首先要考虑清楚编辑的几种操作，整理如下：

if (word1[i - 1] == word2[j - 1])
        不操作
    if (word1[i - 1] != word2[j - 1])
        增
        删
        换

也就是如上4种情况。  
if (word1\[i - 1\] == word2\[j - 1\]) 那么说明不用任何编辑，dp\[i\]\[j\] 就应该是 dp\[i - 1\]\[j - 1\]，即dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\];  
那么就在回顾上面讲过的dp\[i\]\[j\]的定义，word1\[i - 1\] 与 word2\[j - 1\]相等了，那么就不用编辑了，以下标i-2为结尾的字符串word1和以下标j-2为结尾的字符串word2的最近编辑距离dp\[i - 1\]\[j - 1\]就是 dp\[i\]\[j\]了。

if (word1\[i - 1\] != word2\[j - 1\])，此时就需要编辑了，如何编辑呢？  
**操作一：** word1删除一个元素，那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。  
即 dp\[i\]\[j\] = dp\[i - 1\]\[j\] + 1;  
**操作二：** 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”， 最终的操作数是一样！  
**操作三：** 替换元素，word1替换word1\[i - 1\]，使其与word2\[j - 1\]相同，此时不用增删加元素。  
可以回顾一下，if (word1\[i - 1\] == word2\[j - 1\])的时候我们的操作 是 dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\] 对吧。  
那么只需要一次替换的操作，就可以让 word1\[i - 1\] 和 word2\[j - 1\] 相同。  
所以 dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\] + 1;  
综上，当 if (word1\[i - 1\] != word2\[j - 1\]) 时取最小的，即：dp\[i\]\[j\] = Math.min(dp\[i-1\]\[j\]+1,Math.min(dp\[i\]\[j-1\]+1,dp\[i-1\]\[j-1\]+1));

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][j-1]+1,dp[i-1][j-1]+1));
                    }
                }

*  3.dp数组如何初始化

dp\[i\]\[j\] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp\[i\]\[j\]。  
那么dp\[i\]\[0\] 和 dp\[0\]\[j\] 表示什么呢？  
dp\[i\]\[0\] ：以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp\[i\]\[0\]。  
那么dp\[i\]\[0\]就应该是i，对word1里的元素全部做删除操作，即：dp\[i\]\[0\] = i;  
同理dp\[0\]\[j\] = j;

for(int i = 0;i<dp.length;i++){
        
                dp[i][0] = i;
            }
            for(int j = 0;j<dp[0].length;j++){
        
                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  
可以看出dp\[i\]\[j\]是依赖左方，上方和左上方元素的，如图：  
所以在dp矩阵中一定是从左到右从上到下去遍历。  
![在这里插入图片描述][55893e098c8c4f669cb1549de9b42e8a.png]

*  5.举例推导dp数组

以示例1为例，输入：word1 = “horse”, word2 = "ros"为例，dp矩阵状态图如下：  
![在这里插入图片描述][fc6f23d33cea4871a0eb9f7c0140a842.png]

代码实现

class Solution {
        
        public int minDistance(String word1, String word2) {
        
            int[][] dp = new int[word1.length()+1][word2.length()+1];
            for(int i = 0;i<dp.length;i++){
        
                dp[i][0] = i;
            }
            for(int j = 0;j<dp[0].length;j++){
        
                dp[0][j] = j;
            }
            for(int i = 1;i<dp.length;i++){
        
                for(int j = 1;j<dp[0].length;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][j-1]+1,dp[i-1][j-1]+1));
                    }
                }
            }
            return dp[dp.length-1][dp[0].length-1];
        }
    }

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

[72.]: https://leetcode.cn/problems/edit-distance/
[55893e098c8c4f669cb1549de9b42e8a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/ca511a52ec99400cb57407223e2d8f8f.png
[fc6f23d33cea4871a0eb9f7c0140a842.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/bd5b4612a323477ebe8d6f27945752bf.png
[bfb3acb740ba4674bc6f772fa5869a12.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/580fd5b934384295bfb54800d1ad36bb.png