LeetCode 每日一题 72. 编辑距离 动态规划 C++描述

LeetCode 每日一题 72. 编辑距离

大家好,我叫亓官劼(qí guān jié ),三本计算机在读,目前在积极准备21计算机考研中,同时也在学习后端开发,准备工作。不敢孤注一掷,因为要留条后路;不求两全其美在,因为那需要运气+机遇;只求学有所得,慢慢成长。CSDN中记录学习的点滴历程,时光荏苒,未来可期,加油~

2020.04.06 每日一题
难度 困难

题目

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

题解

  这题的话需要我们求解除最少变动的次数,这里提供了3种变动的方法,即增、删、移。这题就没法以暴力大法开头了,因为超时了,所以还是老老实实的DP(动态规划)吧。
  首先我们分析题目,给了我们两个单词word1,word2,分别遍历,对于word1[i]word2[j],我们发现有两种情况:这里使用dp[i][j]表示当word1走到i时,word2走到j时所需要的最少步数。

word1[i] == word2[j]时,那么当前需要的步数和上一步一致即dp[i][j] == dp[i-1][j-1]
word1[i] != word2[j]时,dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j]) + 1
  这样我们的状态转移方程也就有了,下面我们将它写成程序即可:

class Solution {
public:
int minDistance(string word1, string word2) {
int length1 = word1.length();
int length2 = word2.length();
// 如果有一个为空串,则返回另一个不为空的值,即相加
if (length1 * length2 == 0)
return length1 + length2;
// 存放各步需要的最少步数
int dp[length1 + 1][length2 + 1];
// 对边界进行初始化
dp[0][0] = 0;
for(int i = 1; i <= length1; i++)
dp[i][0] = dp[i-1][0] + 1;
for(int j = 1; j <= length2; j++)
dp[0][j] = dp[0][j-1] + 1;
for(int i = 1; i <= length1; i++){
for(int j = 1; j <= length2; j++){
// 这里字符串是从下标0开始的
if(word1[i-1] == word2[j-1])
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = min(min(dp[i-1][j-1],dp[i][j-1]),dp[i-1][j]) + 1;
}
}
return dp[length1][length2];
}
};

运行效率和空间为:
在这里插入图片描述

  状态方程推出来之后,写dp就很简单了,所以核心的还状态转移。PS:LeetCode这几天打卡题越来越不太容易了,刚看题目的时候撸了个暴力,直接超时。。。

作者:亓官劼

相关推荐

使用VSCode开发和调试.NET Core程序的方法

使用VSCode开发和调试.NET Core程序的方法

vscode写python时的代码错误提醒和自动格式化的方法

VSCode写vue项目一键生成.vue模版,修改定义其他模板的方法

Vue项目vscode 安装eslint插件的方法(代码自动修复)

Vue项目vscode 安装eslint插件的方法(代码自动修复)