.net做网站教程,设计美观网站有哪些,移动网站与pc网站,火车头wordpress4.7给你两个单词 word1 和 word2#xff0c; 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作#xff1a;
插入一个字符删除一个字符替换一个字符 这道题也是#xff0c;一眼动态规划#xff0c;乍一看感觉很复杂#xff0c;仔细思考…给你两个单词 word1 和 word2 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作
插入一个字符删除一个字符替换一个字符 这道题也是一眼动态规划乍一看感觉很复杂仔细思考一下还是觉得很复杂。
这道题的dp【i】【j】含义我们设定为word1的前 i 字符串转变为word2的前 j 字符串所需要进行的最小操作数。
当word1和word2中的一个为空时即从空字符串变成另一个字符串或者从一个字符串变为空转换所需的操作数即为另一个单词的长度。
逐一遍历word1的每个字符上遍历word2的每个字符。
当word【i】word【j】时无需做改变。
当word【i】word【j】时我们有三种操作选择增加/删除/替换这三种情况对应着不同的前置情况。
我们用代码来实现思路
对于两个单词word1和word2设dp[i][j]表示word1的前i个字符转换成word2的前j个字符所使用的最少操作数。我们想要计算的最终结果是dp[m][n]其中m和n分别是word1和word2的长度。 初始化当word1和word2中的一个为空时转换所需的操作数即为另一个单词的长度。因此dp[i][0] i0im和dp[0][j] j0jn。 状态转移方程 如果word1[i-1] word2[j-1]注意dp数组的下标从1开始计数而字符串的下标从0开始则dp[i][j] dp[i-1][j-1]因为最后一个字符相同不需要额外操作。如果word1[i-1] ! word2[j-1]则需要考虑三种操作 插入dp[i][j-1] 1删除dp[i-1][j] 1替换dp[i-1][j-1] 1取这三种操作的最小值作为dp[i][j]。
var minDistance function(word1, word2) {const l1word1.length;const l2word2.length;const dpnew Array(l11).fill(0).map(()new Array(l21).fill(0))for(var i1;il1;i)dp[i][0]dp[i-1][0]1;//初始化遍历各种长度的word1变成空字符串的步数只能靠不断删除for(var i1;il2;i)dp[0][i]dp[0][i-1]1;//初始化遍历空字符串长度的word1变成word2的各种长度需要的部署只能靠不断插入//填表for(var i1;il1;i){for(var j1;jl2;j){if(word1[i-1]word2[j-1]){dp[i][j]dp[i-1][j-1];//相等时无需变化}else{dp[i][j]Math.min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])1;//选择使用三种操作最终最少操作数的一种}}}return dp[l1][l2];//输出l1长度的word1即word1变换成l2长度的word2即word2所需要的最小操作数
};
