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

思路

对于字符串 str1 和 str2，dp[i][j]为考虑str1的0~i, str2的0~j的最短编辑距离。

若str1[i] == str2[j]：dp[i][j] = dp[i-1][j-1]若str1[i] != str2[j]，有三种操作，让两个字符串对齐： 1、替换掉这个字符，使得str1[i] == str2[j]，dp[i][j] = dp[i-1][j-1]+12、删去str1中的这个字符，使得问题变为考虑str1[0~i-1]和str2[0~j]对齐问题,dp[i][j] = dp[i-1][j]+13、删去str2[j]，dp[i][j] = dp[i][j-1]+1 综合上面三种情况，找出最小值作为dp[i][j]的值

难点在于边界情况的处理！

代码

代码1：静态数组，内存开销大，86 ms

class Solution { public: int mymin(int a,int b,int c) { return min(min(a,b),c); } int minDistance(string word1, string word2) { int len1 = word1.length(), len2 = word2.length(); int dp[500][500] = {}; int flag1 = 1, flag2 = 1; if(len1 == 0) return len2; if(len2 == 0) return len1; if(word1[0]==word2[0]) { dp[0][0] = 0; flag1 = flag2 = 0; } else dp[0][0] = 1; //1-1:dinitrophenylhydrazine //1-2:phenylhydrazine //2-1:sea //2-2:eat for(int i=1;i<len1;i++) { /*解释下面这个 if 此后只要删除无关字符即可。例如：abcd caret dp[0][1]=1; dp[0][2]=2，而不是3 */ if(word1[i] == word2[0]) { dp[i][0] = i; flag1 = 0; } else dp[i][0] = i+flag1; } for(int j=1;j<len2;j++) { if(word1[0] == word2[j]) { dp[0][j] = j; flag2 = 0; } else dp[0][j] = j+flag2; } for(int i=1;i<len1;i++) { for(int j=1;j<len2;j++) { if(word1[i] == word2[j]) dp[i][j] = dp[i-1][j-1]; else { dp[i][j] = mymin(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1; } } } return dp[len1-1][len2-1]; } };

代码2：动态数组法，节省内存空间，13 ms

class Solution { public: int mymin(int a,int b,int c) { return min(min(a,b),c); } int minDistance(string word1, string word2) { int len1 = word1.length(), len2 = word2.length(); vector<vector<int> > dp; int flag1 = 1, flag2 = 1; if(len1 == 0) return len2; if(len2 == 0) return len1; vector<int> tmp; tmp.push_back(0); dp.push_back(tmp); if(word1[0]==word2[0]) { dp[0][0] = 0; flag1 = flag2 = 0; } else dp[0][0] = 1; //1-1:dinitrophenylhydrazine //1-2:phenylhydrazine //2-1:sea //2-2:eat for(int i=1;i<len1;i++) { /*解释下面这个 if 此后只要删除无关字符即可。例如：abcd caret dp[0][1]=1; dp[0][2]=2，而不是3 */ vector<int> t; if(word1[i] == word2[0]) { t.push_back(i); flag1 = 0; } else t.push_back(i+flag1); dp.push_back(t); } for(int j=1;j<len2;j++) { if(word1[0] == word2[j]) { dp[0].push_back(j); flag2 = 0; } else dp[0].push_back(j+flag2); } for(int i=1;i<len1;i++) { for(int j=1;j<len2;j++) { if(word1[i] == word2[j]) dp[i].push_back(dp[i-1][j-1]); else { dp[i].push_back(mymin(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1); } } } return dp[len1-1][len2-1]; } };

代码3：对边界的处理更熟练，13 ms

class Solution { public: int minDistance(string word1, string word2) { int m = word1.length(), n = word2.length(); vector<vector<int> > dp(m + 1, vector<int> (n + 1, 0)); for (int i = 1; i <= m; i++) dp[i][0] = i; for (int j = 1; j <= n; j++) dp[0][j] = j; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = min(dp[i - 1][j - 1] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j] + 1)); } } return dp[m][n]; } };