LeetCode 每日一题 72. 编辑距离 动态规划 C++描述
大家好，我叫亓官劼（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’)
输入：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这几天打卡题越来越不太容易了，刚看题目的时候撸了个暴力，直接超时。。。
作者：亓官劼
