搭建网站需要哪些东西,wordpress怎么加栏目,杭州优化seo,小制作小发明论文给你两个单词 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)
思路动态规划
dp[i][j]表示word1的前i个字符替换为word2的前j个字符需要多少步
如果word1的第i个字符与word2的第j个字符相同
dp[i][j]dp[i-1][j-1]
否则选择增删改中步骤较小的一步
dp[i][j]min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])1
代码
class Solution { public int minDistance(String word1, String word2) { int m word1.length(); int n word2.length(); int dp[][] new int[m1][n1]; for(int i0;im;i){ dp[i][0] i; } for(int i0;in;i){ dp[0][i] i; } for(int i1;im;i){ for(int j1;jn;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-1][j],dp[i][j-1]),dp[i-1][j-1])1; } } } return dp[m][n]; }
}
