72.编辑距离

72.编辑距离

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

你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符

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

题解： 把字符串A转换成字符串B 最少需要几步完成；转移的方法有三种 删除、插入、替换

思路：使用动态规划求解，难点在于状态定义、状态转移方程的推理
如果想求出矩阵中dp[i][j]的值，只有三条路可以走:从上面 从左面 从左上

逻辑分析.png

假设字符串s1-->"mice" 它的长度为n1, 字符串s2-->"arise"为s2 ,它的长度为n2
dp是大小为(n1+1)*(n2+1)的二维数组, 之所以+1是因为多设立一行和一列可以先求出对应的操作步数，想以此来推导最终的值

如何求出其他位置的bp[i][j] 我们先从最短的mi 转化成a 为例围绕删、增、改来分析 可以得出共4种情况

第一种：
先删除s1[0,i)  的最后一个字符得到 s1[0,i-1) 

然后由s1[0,i-1)转换为s2[0,j) ,这种情况下dp[i][j] = 1 + dp[i-1][j];

第二种: 由s1[0,i) 转换为s2[0,j-1) 然后在最后插入字符s2[j-1],得到s2[0,j)；这种情况下dp[i][j] = dp[i][j-1]+1

第三种： s1[i-1] != s2[j-1] 先由s1[0,i-1] 转换为s2[0, j-1] , 然后将最后以为字符替换,这种情况下 dp[i][j] = dp[i-1][j-1] + 1

第四种：如果s1[i-1] = s2[j-1] 那此时由s1[0,i-1] 转换为s2[0, j-1] 后就不需要再做任何操作了，这种情况下dp[i][j] = dp[i-1][j-1]

//如果想求出矩阵中dp[i][j]的值，只有三条路可以走:从上面 从左面 从左上
class Solution {

   public int minDistance(String word1, String word2) {
       
       //0.边界处理 ，其中一个字符串是空的就没有转换的必要
       if(word1==null||word2==null) return 0;

       //1.定义需要的数据结构
       char[] cs1 = word1.toCharArray();
       char[] cs2 = word2.toCharArray();
       int[][] dp = new int[cs1.length+1][cs2.length+1];
       dp[0][0] = 0;

       //2.1 计算第0行的值
       for(int col = 1;col <= cs2.length;col++) {
         dp[0][col] = col;
       }

       //2.2 计算第0列的值
       for(int row = 1;row <= cs1.length;row++) {
          dp[row][0] = row;
       }

       //3.求出其他行列的值 通过对比得到最小操作数
       for(int i = 1;i <= cs1.length;i++) {
           for(int j = 1;j <= cs2.length;j++) {
               int top = dp[i-1][j]+1;//第一种情况
               int left = dp[i][j-1]+1;//第二种情况
               int leftTop = dp[i-1][j-1];//第四种情况
               if(cs1[i-1] != cs2[j-1]) {//第三种情况
                   leftTop++;
               }
               dp[i][j] = Math.min(Math.min(top,left),leftTop);
           }
       }

       //4.返回结果
       return dp[cs1.length][cs2.length];

   }

}

执行结果.png