资源网站搭建,销售网站内容设计,wordpress 分类目录 不显示,网站做直播吗题意理解#xff1a; 给你两个单词 word1 和 word2#xff0c; 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作#xff1a; 插入一个字符 删除一个字符 替换一个字符 将word1转换为word2,可以进行三种操作#xff1a;增、删、改 给你两个单词 word1 和 word2 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作 插入一个字符 删除一个字符 替换一个字符 将word1转换为word2,可以进行三种操作增、删、改最少操作几次 其中特别注意增和删为互逆操作其效果是一样的在word1删除一个元素或在word2添加一个元素都是进行一次操作效果。 这里我们使用动态规划来进行解题。 解题思路 1定义dp数组 dp[i][j]表示word1第i个元素前word2第j个元素前使word1转换为word2最少需要操作的次数。 2递推公式 当word1[i-1]word2[j-1]时 无需操作 dp[i][j]dp[i-1][j-1] 否则 增|删dp[i-1][j]1 或 dp[i][j-1]1 改 dp[i-1][j-1]1 即 dp[i][j]Math.min(Math.min(dp[i-1][j]1 ,dp[i][j-1]1), dp[i-1][j-1]1 ) (3) 初始化 dp[i][0] 表示把word1变为空串则产出i个元素即dp[i][0]i 同理 dp[0][j]j 1.动态规划解题
public int minDistance(String word1, String word2) {int [][] dpnew int[word1.length()1][word2.length()1];for(int i0;iword1.length();i){dp[i][0]i;}for(int j1;jword2.length();j){dp[0][j]j;}for(int i1;iword1.length();i){for(int j1;jword2.length();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])1,dp[i-1][j-1]1);}}}return dp[word1.length()][word2.length()];}
2.复杂度分析 时间复杂度O(n^2) 空间复杂度O(n^2)
