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
public class Solution { public int minDistance(String word1, String word2) { // Start typing your Java solution below // DO NOT write main() function int m = word1.length(), n = word2.length(); int[][] dp = new int[m+1][n+1]; dp[0][0] = 0 ; for(int i = 1; i<=m ; i++){ dp[i][0] = i; } for(int i = 1; i <= n ;i++){ dp[0][i] = i; } for(int i = 1 ; i <= m ; i++){// notice m for(int j =1; j <= n; j++){// notice n if(word1.charAt(i-1) == word2.charAt(j-1)){ dp[i][j] = dp[i-1][j-1]; } else{ dp[i][j] = 1 + Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1])); } } } return dp[m][n]; } }
public static int rec(String word1, int len1, String word2, int len2){//recursion if(len1 == 0){ return len2; } if(len2 == 0){ return len1; } if(word1.charAt(len1-1) == word2.charAt(len2-1)){ return rec(word1, len1-1, word2, len2-1); }else{ return 1+ min3(rec(word1, len1-1, word2, len2-1), rec(word1, len1, word2, len2-1) ,rec(word1, len1-1, word2, len2) ); } }
mistakes:1)边界case,since we are looking for last element in string ,so two loops has to be equal to m/n
learned: 这个一看就知道是要用动态规划法的，但是问题是如何填表。
难点就是在两个字母相同的时候，直接复制左上角的元素下来就可以了。这个条件还是很难想出来的。
理解起来应该是当两个字母相同的时候，就是不用增加1个距离，那么直接复制前面的修改单词方案就可以了。
当两个字母不相同的时候，就需要增加一个修改距离，那么就需要在前面三种方案中选择最小的一种方案加1.
动态规划法，原始填二维表法：