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

72. 编辑距离

• 题目
• 解题思路
• 代码

题目

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

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

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

解题思路

这是对两个字符串进行动态规划的操作，这种题目的思路就是建立一个二维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] 表示插入操作。

注意，针对第一行，第一列要单独考虑，我们引入了" "。
①第一行，是 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));
    }
}