day112（3.14）——leetcode面试经典150

72. 编辑距离

72. 编辑距离

题目：

题解：

class Solution { public int minDistance(String word1, String word2) { char[] w1 = word1.toCharArray(); char[] w2 = word2.toCharArray(); int[][] dp = new int[w1.length+1][w2.length+1]; //进行设置初始：当i==0时，这说明word1此时没字符，那么只能通过插入字符来实现单词word2 //当j==0时，这说明此时word2没有字符，那么只能通过删除word1来实现word2 //具体要插入替换的次数是根据字符串长度进行增加的 for(int i=0;i<=w1.length;i++) { dp[i][0]=i; } for(int i=0;i<=w2.length;i++) { dp[0][i]=i; } //进行递堆 //状态转移方程是：如果当前i和j的字符相等，此时需要的最小步数就是dp[i-1][j-1] //如果当前i和j的字符不相等，也意味着，可以通过插入，删除，替换三种方式来使他们相等，只需要找到当前最小的步骤的方式，再加上1 //这就意味着此时（i-1，j）->（i，j）的操作是删除 //（i，j-1）-> (i，j)的操作是插入 //（i-1，j-1）-> (i,j)的操作是替换 //理清楚了这里就可以直接写代码 for(int i=1;i<=w1.length;i++) { for(int j=1;j<=w2.length;j++) { if(w1[i-1]==w2[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[w1.length][w2.length]; } }