首页 > 代码库 > 【leetcode刷题笔记】Edit Distance
【leetcode刷题笔记】Edit Distance
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
题解：动态规划问题。
用数组dp[i][j]表示从word1[0,i]变换到word2[0,j]所需要的最小变换。
那么dp[i][j] = word1(i) == word2(j)? dp[i-1][j-1]: min(dp[i-1,j], dp[i,j-1], dp[i-1,j-1])+1；
要特别注意的是第一行和第一列的处理问题。一种方法是把dp的大小设置为dp[word1.length+1][word2.length+1],然后dp[0][i] = dp[i][0] = i，表示从空字符串变换到长度为i的字符串相互变换至少需要i步。个人觉得这是比较好的一种方法，但是当时没有想到。
我想到的是另外 一种方法，而且在这里被坑了好久。以行为例： dp[0][i] = Math.max(dp[0][i-1] + (wordchars1[0]== wordchars2[i]?0:1),i); 表示如果word1的第0个字符和word2的第i个字符相等，那么需要dp[0][i-1]步变换。但是这里有个问题，就是当word1 = "pneumu", word2 = "up"的时候，此时从字符串"u"变换到"pneum"需要4步，在计算从"u"变换到"pneumu"的时候，如果直接用dp[0][i-1]得到需要4步，但这是不可能的，因为两个字符串的长度就相差了5，至少需要5步，所以才有了外面的max函数判断，两个字符串互相转换的最少步数不会低于两个字符串长度之差。
最终代码如下：
1 public class Solution { 2 public int minDistance(String word1, String word2) { 3 int m = word1.length(); 4 int n = word2.length(); 5 if(m == 0) 6 return n; 7 if(n == 0) 8 return m; 9 int[][] dp = new int[m][n];10 11 char[] wordchars1 = word1.toCharArray();12 char[] wordchars2 = word2.toCharArray(); 13 14 dp[0][0] = wordchars1[0] == wordchars2[0]?0:1;15 for(int i = 1;i < n;i++)16 dp[0][i] = Math.max(dp[0][i-1] + (wordchars1[0]== wordchars2[i]?0:1),i);17 for(int i = 1;i < m;i++)18 dp[i][0] = Math.max(dp[i-1][0] + (wordchars1[i]== wordchars2[0]?0:1),i);19 20 for(int i = 1;i < m;i++){21 for(int j = 1;j < n;j++){22 if(wordchars1[i] == wordchars2[j] )23 dp[i][j] = dp[i-1][j-1];24 else{25 dp[i][j] = 1 + Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]));26 }27 }28 }29 30 return dp[m-1][n-1];31 }32 }