本文主要是介绍Leetcode面试经典150题-72.编辑距离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
解法都在代码里，不懂就留言或者私信
动态规划最经典题之一，如果写不出来，动态规划好好再学学
class Solution {/**这个题是动态规划最经典的题，另一个最经典的是背包问题 */public int minDistance(String word1, String word2) {/**如果一个为0，取另外一个的长度就可以了 */if(word1.length() == 0 || word2.length() == 0) {return word1.length() == 0? word2.length() : word1.length();}/**转成字符数组方便操作*/char[] wordArr1 = word1.toCharArray();char[] wordArr2 = word2.toCharArray();/**dp[i][j]表示word1的前i个字符转换成word2的前j个字符的最少操作数，这里注意数组的长度 */int[][] dp = new int[wordArr1.length + 1][wordArr2.length + 1];/**初始化第一行，也就是dp[0][j]，就是word1的前0个字符编辑成word2的前j个字符的代价，当然j是多少就需要多少次操作（添加） */for(int j = 0; j < dp[0].length; j++) {dp[0][j] = j;}/**初始化第一列,也就是dp[i][0]，就是word1的前i个字符编辑成word2的前0个字符的代码，有多少删除多少呗，还能咋样*/for(int i = 0; i < dp.length; i++) {dp[i][0] = i;}/**初始化一般位置，对于一般位置，有两种操作路径：1.使用word1的前i-1个字符编辑成word2的前j个字符，然后删除word1的i位置字符2.使用word1的前i个字符编辑成word2的前j-1个字符，然后加上word2的j位置字符3.word1的前i-1编辑成word2的前j-1，然后i位置的字符替换为j位置的字符（如果相同代价为0）两个谁代价小要谁 */for(int i = 1; i < dp.length; i++) {for(int j = 1; j < dp[i].length; j++) {/**这里我把1，2他们写一起了，以为本题什么操作代价都相同，所以1我写在最后了，如果你觉得不舒服可以改成min函数里各加1各1 */dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + 1;/**把情况3和1，2的结果比以下 */dp[i][j] = Math.min(dp[i][j], dp[i-1][j-1] + (wordArr1[i-1] == wordArr2[j-1]? 0 : 1));}}/**返回word1的整个长度编辑成word2的整个长度的代价 */return dp[wordArr1.length][wordArr2.length];}
}勉勉强强的结果
这篇关于Leetcode面试经典150题-72.编辑距离的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
