【算法题】编辑距离(动态规划)，一文彻底弄懂！

目录

一、题目描述

二、解题思路 

三、参考答案

---

一、题目描述

      编辑距离

给你两个单词 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、首先确定DP数组以及它的含义

        这里我们使用一个二维的DP数组dp[i][j]，此时dp[i][j]就表示word1和word2对应的i和j位置结束的时候转换后的最少操作次数。比如word1为abc，word2为dcdb，则dp[1][3]就表示ab转换成dcdb的最少转换次数。这个dp[i][j]的含义一定要记住，不然后面再推导递推公式的时候就很容易把自己绕晕！

   2、如何初始化dp数组

        首先我们要确定，我们要初始化dp数组的哪些位置。因为我们的dp[i][j]表示的是word1和word2对应的i和j位置结束的时候转换后的最少操作次数。所以，最终的我们要的结果也就是dp二维数组的最后一个元素。

 所以，这里我们需要初始化dp数组的第一行和第一列。这样，最终我们才能根据第一行和第一列的数据来推导出来最终的结果。

        那么，问题来了，我们该如何初始化第一行和第一列的数据呢？

       比如，word1为abc，word2为dcdb。我们初始化第一行的时候，那就是要求出a分别转换成d、dc、dcd、dcdb时的最少操作次数。显然这样初始化是非常麻烦的，甚至是不可完成的！那么我们再假设word1为zabc，word2为zdcdb。此时我们初始化第一行的时候，则就是求z分别转换成z、zd、zdc、zdcd、zdcdb时的最少操作次数。显然这个时候就很简单了对应最少操作次数其实就是j的值。

        那么，灵感来了!

        我们只要对word1和word2分别在它的首位置都添加一个相同的字符就行了！因为两个字符相同，所以不会影响我们最终的结果的。此时初始化dp数组就如下：

        // 初始化第一行
        for (int j = 0; j < n; j++)
            dp[0][j] = j;
        // 初始化第一列
        for (int i = 0; i < m; i++)
            dp[i][0] = i;

注：m是word1单词的长度，n是word2单词的长度。 

   3、确定递推公式

• 当前遍历的dp[i][j]对应word1和word2位置上的字符相等的时候

           dp[i][j] = dp[i-1][j-1] 
      此时不需要任何操作，所以此时的 dp[i][j] = dp[i-1][j-1] 

• 当前遍历的dp[i][j]对应word1和word2位置上的字符不相等的时候，此时就需要进行操作

        1）插入、删除

        插入和删除操作是等价的，比如a和ab我们删除b和添加b操作次数都是一样的。所以这里我们只考虑删除即可。删除有可能删除word1的i位置的元素，也有可能删除word2的j位置的元素，删除word1和删除word2对应的操作次数是不一样的，所以需要比较出一个操作次数少的。
       删除word1的i位置的元素：dp[i][j] = dp[i-1][j]+1
       删除word2的j位置的元素：dp[i][j] = dp[i][j-1]+1 

       此时在当前操作下的最少操作次数就是：

     dp[i][j] =  Math.min(dp[i-1][j]+1, dp[i][j-1]+1);

      如果此时有点晕，一定要再想dp[i][j]代表的是什么！

       2）替换

       替换也就是将word1在i位置的字符替换成word2在j位置的字符或者是将word2在j位置的字符替换成word1在i位置的字符。不管它俩谁替换谁，我们最终关心的只是操作次数。所以，这里也就是1次操作。所以，我们只要在它们俩前一个位置上的时的最少操作次数上面加1，也就是word1和word2在当前位置和当前替换操作下的最少操作次数了。

        dp[i][j] = dp[i-1][j-1]+1

最后，我们求出这些操作中哪个操作次数最少，也就是我们最终该位置上的最少操作次数了。也就是在word1和word2在i和j位置上的字符不相等的时候的递推公式了。

dp[i][j] =  Math.min( dp[i-1][j-1]+1, Math.min(dp[i-1][j]+1, dp[i][j-1]+1));

三、参考答案

class Solution {
    public int minDistance(String word1, String word2) {
        // 两个字符串前面都加个空字符串，方便后续初始化二维dp数组
        word1 = " " + word1;
        word2 = " " + word2;
        char[] word1Array = word1.toCharArray();
        char[] word2Array = word2.toCharArray();
        int m = word1Array.length, n = word2Array.length;
        // 定义一个dp二维数组,dp[i][j]表示word1和word2对应的i和j位置的时候最少操作次数
        int[][] dp = new int[m][n];
        // 初始化dp数组
        // 初始化第一行
        for (int j = 0; j < n; j++)
            dp[0][j] = j;
        // 初始化第一列
        for (int i = 0; i < m; i++)
            dp[i][0] = i;
        // 遍历
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 当当前位置相等的时候
                if (word1Array[i] == word2Array[j]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else { // 不相等的时候需要处理
                   dp[i][j] = Math.min(Math.min(dp[i][j-1],dp[i-1][j-1]),dp[i-1][j])+1;
                }
            }
        }
        return dp[m-1][n-1];
    }
}

       以上就是使用动态规划解决力扣上72题编辑距离的方法。通过使用动态规划，我们可以高效地解决这个问题，时间复杂度为O(m*n)，其中m和n分别是字符串word1和word2的长度。编辑距离是一个非常有意义的问题，掌握了解决方法后，我们就可以将其应用到各种实际问题中，提高算法的效率。编辑距离在我们的实际开发中有很多的应用场景，比如拼写纠错、数据对齐、抄袭侦测等。