72. 编辑距离（动态规划）

深碍√TFBOYSˉ_ 2023-10-05 19:25 80阅读 0赞

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

*  题目
 *  解题思路
 *  代码

## 题目 ##

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

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]

## 解题思路 ##

这是对两个字符串进行动态规划的操作，这种题目的思路就是建立一个二维dp表。本题也是。首先定义dp\[\]\[\]的含义：`存储着s1[0..i-1]、s2[0..j-1]的最小编辑距离`。用两个指针分别遍历s1,s2，那么有两种大情况

*  s1\[i\]==s2\[j\]  
    此时dp\[i\]\[j\] = dp\[i-1\]\[j-1\]；即不用进行操作，直接跳过这两个字符
 *  s1\[i\] != s\[j\]  
    那么就可以选择做插入字符，删除字符，替换字符的操作，从这三个里面取一个编辑距离最小的。其中，dp\[i-1\]\[j-1\] 表示替换操作，dp\[i-1\]\[j\] 表示删除操作，dp\[i\]\[j-1\] 表示插入操作。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]  
注意，针对第一行，第一列要单独考虑，我们引入了`" "`。  
①第一行，是 s1 为空变成 s2 最小编辑距离，就是插入操作。也可以理解为s1走完了，s2还没走完，那么就把s2剩余的字符都插入到s1中。

②第一列是 s2 为空，需要的最小编辑距离，就是删除操作。也可以理解为s2走完了，s1还没走完，那么就需要删除操作把s1缩短为s2.

以上两个就是base case。

## 代码 ##

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];
            
            //base case  没太理解
            for(int i=1;i<=m;i++){
        
                dp[i][0]=i;
            }
            for(int j=1;j<=n;j++){
        
                dp[0][j]=j;
            }
    
            for(int i=1;i<=m;i++){
        //dp表中下标0是base case，所以这里下标1其实是字符串的第一个字符
                for(int j=1;j<=n;j++){
        
                   
                    if(word1.charAt(i-1)==word2.charAt(j-1)){
        
                        //word1.charAt(i-1)：i=1时，i-1=0；所以是字符串中的第一个字符
                        dp[i][j]=dp[i-1][j-1];
                    }else{
        
                        dp[i][j]=min(dp[i-1][j]+1,//删除
                                    dp[i][j-1]+1,//插入
                                    dp[i-1][j-1]+1//替换
                                    );
                    }
                }
    
            }
        return dp[m][n];//存储着整个s1和s2的最小编辑距离
        }
    
        public int min(int a,int b,int c){
        
            return Math.min(a,Math.min(b,c));
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210207224324415.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210207224428994.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70