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
分析：用动态规划来解，f[i][j]表示word1[0,i-1]与word2[0,j-1]的edit distance。当word1[i] == word2[j]时，f[i][j] = f[i-1][j-1]；否则，f[i][j]为f[i-1][j]+1（delete a character）、f[i][j-1]+1（insert a character）、f[i-1][j-1]+1（replace a character）中的最小值。
1 class Solution { 2 public: 3 int minDistance(string word1, string word2) { 4 int m = word1.length(), n = word2.length(); 5 if(m == 0 || n == 0) return abs(m-n); 6 int record[m+1][n+1]; 7 for(int i = 0; i <= m; i++) 8 record[i][0] = i; 9 for(int j = 0; j <= n; j++) 10 record[0][j] = j; 11 for(int i = 1; i <= m; i++) 12 for(int j = 1; j <= n; j++){ 13 if(word1[i-1] == word2[j-1]) record[i][j] = record[i-1][j-1]; 14 else{ 15 int min_step = min(record[i-1][j],record[i][j-1]); 16 record[i][j] = min(min_step,record[i-1][j-1]) + 1; 17 } 18 } 19 return record[m][n]; 20 } 21 };
原文：http://www.cnblogs.com/Kai-Xing/p/3926854.html