佛山免费建站公司,金融公司网站建设模板,网站的支付系统怎么做的,巨人科技网站建设给你两个单词word1和word2#xff0c;请返回将word1转换成word2所使用的最少操作数。 你可以对一个单词进行如下三种操作#xff1a; 插入一个字符删除一个字符替换一个字符 示例1#xff1a; 输入#xff1a;word1 horse, word2 ros
输出#… 给你两个单词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 由小写英文字母组成 题解 动态规划 1.自底向上的递推法从起点状态开始扫描输出值为终点状态值需要填整个动态规划状态表尽管不是所有的状态都对终点状态的计算有直接贡献有些状态其实没有必要计算。递推填表的时间复杂度OM*N,空间复杂度可以从OM*N优化到ON。 2.自顶向下的递推法从终点状态开始调用递归扫描所有必需的状态空间只需要填一部分的动态规划表有些不必要的状态可以直接避免计算。这里的递归法其实是一种深度优先的办法去扫描动态规划的有效状态空间。对于递归过程中的重复计算可以用记忆性方法剪枝来提高效率。记忆化递归的平均时间复杂度OM*N,但是时间常数项比递推填表的要小一半速度更快极端情况下记忆化递归的时间复杂度可以将为ON但是空间复杂度不能优化为OM*N。 动态规划的状态空间dp是二维状态空间数组由word1和word2张开最开始补一位空字符 dp[i][j]代表word1的前i-1个字符的子串与word2的前j-1个字符的子串的编辑距离。 题意简单讲就是对应字符相同则不用编辑字符不同则需要编辑。状态转移为 若最右边的字符相同则不用编辑字符退化到均减少一个字符的状态 dp[i][j] dp[i-1][j-1] 若最右边的字符不同则通过一次增删或替换操作联系到其他状态 dp[i][j] 1min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) 其中dp[i-1][j]是删除操作dp[i][j-1]是插入操作dp[i-1][j-1]是替换操作 初始条件 dp[i][0] i; dp[0][j]j; 动态规划----递推填表 以word1 horse, word2 ros为例
dp [[0, 1, 2, 3], [1, 1, 2, 3], h[2, 2, 1, 2], o[3, 2, 2, 2], r[4, 3, 3, 2], s[5, 4, 4, 3]] e r o s
是最开始补的一位空字符。
又比如对于word1 horse, word2 horse
dp [[0, 1, 2, 3, 4, 5], [1, 0, 1, 2, 3, 4], h[2, 1, 0, 1, 2, 3], o[3, 2, 1, 0, 1, 2], r[4, 3, 2, 1, 0, 1], s[5, 4, 3, 2, 1, 0]] e h o r s estatic inline int Min(const int a, const int b, const int c) {int min (a b) ? a : b;return (min c) ? min : c;
}int minDistance(char * word1, char * word2){int m strlen(word1), n strlen(word2);int dp[m 1][n 1];for (int i 0; i m 1; i) {dp[i][0] i;}for (int j 1; j n 1; j) {dp[0][j] j;}for (int i 1; i m 1; i) {for (int j 1; j n 1; j) {if (word1[i - 1] word2[j - 1]) {dp[i][j] dp[i - 1][j - 1];} else {dp[i][j] 1 Min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);}}}return dp[m][n];
}
