同声传译公司网站建设,自己能够做投票网站吗,招聘网站可做哪些推广方案,wordpress网站是什么意思题目#xff1a;
链接#xff1a;LeetCode 72. 编辑距离 难度#xff1a;中等
给你两个单词 word1 和 word2#xff0c; 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作#xff1a;
插入一个字符删除一个字符替换一个字符
示例…题目
链接LeetCode 72. 编辑距离 难度中等
给你两个单词 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 500word1 和 word2 由小写英文字母组成
解题思路
详见《Hello 算法》编辑距离问题
代码
class Solution {
public:int minDistance(string word1, string word2) {int n word1.size();int m word2.size();vectorvectorint dp(n 1, vectorint(m 1));for (int i 1; i n; i) dp[i][0] i; // 插入n个字符的操作数for (int j 1; j m; j) dp[0][j] j;for (int i 1; i n; i) {for (int j 1; j m; j) {if (word1[i - 1] ! word2[j - 1]) {dp[i][j] min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) 1; // 对应插入、删除、替换三种操作} else {dp[i][j] dp[i - 1][j - 1]; // 相同字符不需要操作}}}return dp[n][m];}
};时间复杂度O(NM)空间复杂度O(NM)。N、M为字符串 word1 和 word2 的长度。
