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
Dynamic Programming String
注意项：
我写的如下：
1 #include <iostream> 2 #include <string> 3 #include <memory.h> 4 using namespace std; 5 6 class Solution { 7 public: 8 int minDistance(string word1, string word2) { 9 int len1 = word1.length(),len2=word2.length(); 10 if(len1==0) return len2; 11 if(len2==0) return len1; 12 int **dpmap = new int *[len1+1]; 13 dpmap[0] =new int[(len1+1)*(len2+1)]; 14 memset(dpmap[0],0,sizeof(int)*(len1+1)*(len2+1)); 15 for(int i= 1;i<=len1;i++) 16 dpmap[i] = dpmap[i-1]+len2+1; 17 for(int i=0;i<=len1;i++) 18 dpmap[i][0] = i; 19 for(int j=0;j<=len2;j++) 20 dpmap[0][j] = j; 21 for(int i=1;i<=len1;i++){ 22 for(int j=1;j<=len2;j++){ 23 if(word1[i-1]==word2[j-1]) dpmap[i][j]=dpmap[i-1][j-1]; 24 else{ 25 dpmap[i][j]=(dpmap[i-1][j]>dpmap[i][j-1]?dpmap[i][j-1]:dpmap[i-1][j])+1; 26 if(dpmap[i-1][j-1]+1<dpmap[i][j]) 27 dpmap[i][j] = dpmap[i-1][j-1]+1; 28 } 29 } 30 } 31 int ret = dpmap[len1][len2]; 32 // for(int i=0;i<=len1;i++){ 33 // for(int j=0;j<=len2;j++) 34 // cout<<dpmap[i][j]<<" "; 35 // cout<<endl; 36 // } 37 delete []dpmap[0]; 38 delete []dpmap; 39 return ret; 40 } 41 }; 42 43 int main() 44 { 45 string word1 = "123"; 46 string word2 = "111"; 47 Solution sol; 48 cout<<sol.minDistance(word1,word2)<<endl; 49 return 0; 50 }
原文：http://www.cnblogs.com/Azhu/p/4128242.html
