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:
- Insert a character
- Delete a character
- Replace a character
Example
Given word1 = "mart" and word2 = "karma", return 3.
教科书上的DP问题 不废话 直接上code
1 public class Solution { 2 /** 3 * @param word1 & word2: Two string. 4 * @return: The minimum number of steps. 5 */ 6 public int minDistance(String word1, String word2) { 7 // write your code here 8 if(word1==null&&word2==null) { 9 return 0; 10 } 11 else if(word1!=null&&(word2==null||word2.length()==0)){ 12 return word1.length(); 13 } else if ((word1==null||word1.length()==0)&&word2!=null){ 14 return word2.length(); 15 } 16 17 int len1 = word1.length(); 18 int len2 = word2.length(); 19 20 int[][] t = new int[len1][len2]; 21 22 int i=0; 23 for(; i< len2;i++){ 24 if(word1.charAt(0)==word2.charAt(i)){ 25 t[0][i] = i; 26 break; 27 }else{ 28 t[0][i] = i+1; 29 } 30 } 31 for(;i<len2;i++){ 32 t[0][i] = i; 33 } 34 i=0; 35 for(; i< len1;i++){ 36 if(word2.charAt(0)==word1.charAt(i)){ 37 t[i][0] = i; 38 break; 39 }else{ 40 t[i][0] = i+1; 41 } 42 } 43 for(;i<len1;i++){ 44 t[i][0] = i; 45 } 46 47 for(i=1; i< len1;i++){ 48 for( int j=1;j<len2;j++){ 49 if(word1.charAt(i)==word2.charAt(j)){ 50 t[i][j] = Math.min(t[i-1][j-1], Math.min(t[i-1][j]+1, t[i][j-1]+1)); 51 }else{ 52 t[i][j] = Math.min(t[i-1][j-1], Math.min(t[i-1][j], t[i][j-1]))+1; 53 } 54 } 55 } 56 return t[len1-1][len2-1]; 57 } 58 }