成都网站品牌设计,佛山品牌网站设计,网站开发常用中间件,中小企业如何建设网站今日份题目#xff1a;
给你两个单词 word1 和 word2#xff0c; 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作#xff1a; 插入一个字符 删除一个字符 替换一个字符
示例1
输入#xff1a;word1 horse, word…今日份题目
给你两个单词 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 由小写英文字母组成
题目思路
动态规划将整个单词的编辑问题转换成三个子问题的编辑问题。
思路插入、删除、替换三个操作可以在word1和word2两个单词中分别操作并且word1的插入操作就是word2的删除操作同理word2的插入操作就是word1的删除操作所以双方的六个操作可以简化为word1的插入操作、word2的插入操作和替换操作三个操作。假设当前位置是word1的第i个字符、word2的第j个字符。所谓word1的插入操作就是在i-1和j的位置的基础上也就是word1的前i-1个字符和word2的前j个字符编辑的距离的子问题下对word1进行插入操作所谓word2的插入问题就是在i和j-1的位置的基础上也就是word1的前i个字符和word2的前j-1个字符编辑的距离的子问题下对word2进行插入操作所谓替换操作就是在i-1和j-1的位置的子问题下对当前字符进行判断是否需要替换如果字符不同就需要替换相同就不需要替换注意dp中的i是word中的i-1因为word从0开始遍历下标dp从1开始遍历下标。
接下来就是大家比较关心的状态转移方程问题
根据上段的分析我们知道会有三种状态三种操作对应三种状态
//word1插入字符word1的前i-1个字符和word2的前j个字符编辑的距离本次word1插入1个字符
int adp[i-1][j]1;
//word2插入字符word1的前i个字符和word2的前j-1个字符编辑的距离本次word2插入1个字符
int bdp[i][j-1]1;
//替换word1的前i-1个字符和word2的前j-1个字符编辑的距离本次替换字符
int cdp[i-1][j-1];
if(word1[i-1]!word2[j-1]) c1;
//如果word1的第i个字符word的下标为i-1和word2的第j个字符word的下标为j-1相同就不需要进行替换修改操作
状态转移方程就是取操作后的最小状态因为要求最小操作距离
dp[i][j]min(a,min(b,c));
状态转移方程对比 最后dp [ n ] [ m ] 就是我们要返回的答案。
这道题目比较困难思路也可能存在漏洞欢迎大家在评论区进行讨论谢谢
代码
class Solution
{
public:int minDistance(string word1, string word2) {//获取两个字符串的长度int nword1.length();int mword2.length();//有一个字符串为空串if(n0) return m;else if(m0) return n;//dp数组int dp[1000][1000]{0};//边界状态初始化for(int i0;in;i) {dp[i][0]i;//相对于word1执行i次删除操作}for(int j0;jm;j) {dp[0][j]j;//相对于word1执行j次插入操作}//计算所有dp值for(int i1;in;i) {for(int j1;jm;j) {//word1的前i-1个字符和word2的前j个字符编辑的距离本次word1插入1个字符int adp[i-1][j]1;//word1的前i个字符和word2的前j-1个字符编辑的距离本次word2插入1个字符int bdp[i][j-1]1;//word1的前i-1个字符和word2的前j-1个字符编辑的距离本次替换字符int cdp[i-1][j-1];//如果word1的第i个字符word的下标为i-1和word2的第j个字符word的下标为j-1相同就不需要进行替换修改操作if(word1[i-1]!word2[j-1]) c1;dp[i][j]min(a,min(b,c));}}return dp[n][m];}
};提交结果 欢迎大家在评论区讨论如有不懂的代码部分欢迎在评论区留言
