关键词查网站,上海专业的网络推广,国内手机网站建设,阿里云服务器做网站需要备案题目介绍
给你两个单词 word1 和 word2#xff0c; 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作#xff1a;
插入一个字符删除一个字符替换一个字符
示例 1#xff1a;
输入#xff1a;word1 horse, 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 500word1 和 word2 由小写英文字母组成
解答
class Solution {
public:int minDistance(string word1, string word2) {// dp[i][j] 表示以word1中下标 i-1 结尾的字符串 和 以word2中下标 j-1 为结尾的字符的最近编辑距离// if(word1[i - 1] word2[j - 1]) dp[i][j] dp[i - 1][j - 1];// if(word1[i - 1] ! word2[j - 1])// 操作1word1删除一个元素那么就是以下标i - 2为结尾的word1 与 以j-1为结尾的word2的最近编辑距离 1,即 dp[i][j] dp[i - 1][j] 1;// !!!操作2 word2删除一个元素(相当于word1添加一个元素)那么就是以下标i - 1为结尾的word1 与 以j-2为结尾的word2的最近编辑距离 1,即 dp[i][j] dp[i][j - 1] 1;// 操作3替换元素word1替换 word1[i - 1]使其与 word2[j - 1] 同此时只需要求得两字符串前面部分的最小编辑距离即 dp[i][j] dp[i - 1][j - 1] 1;// 综上取三个操作的最小者// 注意word1删除元素变为word2,和word2添加元素变为word1操作步骤是一样的vectorvectorint dp(word1.size() 1, vectorint(word2.size() 1, 0));// 由于dp[i][j] 是由其上方和左边元素推导所以初始化第一行和第一列// dp[i][0] 表示以word1[i - 1] 结尾的字符串 和 以 word2[-1] 的字符串的最近编辑距离for(int i 0; i word1.size(); i) dp[i][0] i; // 删除i次for(int j 0; j word2.size(); j) dp[0][j] j;for(int i 1; i word1.size(); i){for(int j 1; j word2.size(); j){if(word1[i - 1] word2[j - 1]) dp[i][j] dp[i - 1][j - 1];else dp[i][j] min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) 1;}}return dp[word1.size()][word2.size()];}
};
