比较专业的建设网站的公司,短视频营销ppt,创意包装设计,如何更改网站标签logo题目
给你两个单词 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) {int m word1.length(), n word2.length();int[][] dp new int[m 1][n 1];for (int i 0; i m 1; i) {dp[i][0] i;}for (int i 0; i n 1; i) {dp[0][i] i;}for (int i 1; i m 1; i) {for (int j 1; j n 1; j) {if (word1.charAt(i - 1) word2.charAt(j - 1)) {dp[i][j] dp[i - 1][j - 1];} else {dp[i][j] Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) 1;}}}return dp[m][n];}
}
总结
动态规划
dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数
所以
当 word1[i] word2[j]dp[i][j] dp[i-1][j-1]
当 word1[i] ! word2[j]dp[i][j] min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) 1
其中dp[i-1][j-1] 表示替换操作dp[i-1][j] 表示删除操作dp[i][j-1] 表示插入操作。
注意针对第一行第一列要单独考虑我们引入 word.charAt(0) 。
