☆打卡算法☆LeetCode 72、编辑距离 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定两个单词，计算出单词1转换为单词2所最少操作数。”

题目链接：

来源：力扣（LeetCode）

链接：72. 编辑距离 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

给你两个单词 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')

二、解题

1、思路分析

找出所有解，可以用动态规划。

对于任意一个单词进行插入删除替换操作，转换成第二个单词即可。

2、代码实现

代码参考：

public class Solution {
    public int MinDistance(string w1, string w2) {
        //【dp数组定义】w1转为w2所需的最小操作数
        int[,] dp = new int[w1.Length + 1, w2.Length + 1];
        //【初始化】
        for (int i = 0; i <= w1.Length; i++) dp[i, 0] = i;
        for (int j = 0; j <= w2.Length; j++) dp[0, j] = j;
        //【状态转移】
        for (int i = 1; i <= w1.Length; i++)
        {
            for (int j = 1; j <= w2.Length; j++)
            {
                if (w1[i - 1] == w2[j - 1])
                    //如果最后一位相等，最少操作数无影响
                    dp[i, j] = dp[i - 1, j - 1];
                else
                    //如果不相等，到d[i,j]一共有3种状态，取最小：替换、w1新增w2的最后1位、w2新增w1的最后1位
                    dp[i, j] = Math.Min(dp[i - 1, j - 1], Math.Min(dp[i - 1, j], dp[i, j - 1])) + 1;
            }
        }
        return dp[w1.Length, w2.Length];
    }
}

3、时间复杂度

时间复杂度 ： O(n)

其中n是数组的长度，只需要遍历一遍数组即可求得答案。

空间复杂度： O(1)

只需要常数级别的空间存放变量。

三、总结

1.选择什么套路来做？题目是序列的处理问题，一般带有“最少”“最多”“最大”“子序列”等可以一步步解决的字符串或数组问题，可以考虑用DP，2个序列的比较，用dp[i,j]二维数组；

2.再想DP数组的含义是什么，一般就是按问题描述，比如本题dp[i,i]就是将长度为i的word1 转换成长度为j的word2 所使用的最少操作数；

3.既然使用了dp[i,j]，就要想这种状态是怎么得来的，即状态转移方程，就要分情况了，一般是先比较两个序列的最后1位，是否相等，针对本题：

如果最后1位相等：则删除或新增这1位，对最少操作数没有影响，即dp[i,j] = dp[i-1,j-1];

如果最后1位不相等，如何让它们相等？有下面这几种情况：

• Ⅰ：替换最后1位，无论替换哪个操作数都是1：dp[i,j] = dp[i-1,j-1]+1；
• Ⅱ：第1个数组新增1位，使最后1位与第2个数组的最后1位相等：dp[i,j] = dp[i-1,j]+1；
• Ⅲ：第2个数组新增1位，使最后1位于第1个数组的最后1位相等：dp[i,j] = dp[i,j-1]+1；

同时，时刻想清楚dp[i,j]、dp[i-1,j-1]、dp[i-1,j-1]、dp[i,j-1]的含义即可。