[LeeCode]Edit Distance

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

经典DP ，引wiki:

      d[i, j] := 最小值(
                                d[i-1, j  ] + 1,     // 刪除
                                d[i  , j-1] + 1,     // 插入
                                d[i-1, j-1] + cost   // 替換

   若 str1[i] = str2[j] 則 cost := 0
                                否則 cost := 1

)

编程之美上也有详细阐述，算法导论习题。

代码如下：

class Solution {
public:
    int minDistance(string word1, string word2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int len1 = word1.size();
		int len2 = word2.size();
		if(len1==0)
			return len2;
		if(len2==0)
			return len1;
		vector <vecotr <int> > f(len1+1,vector<int>(len2+1));
		for(int i = 0 ; i <= len1 ; i++)
			f[i][0] = i;
		for(int j =0 ; j <= len2 ; j++)
			f[0][j] = j;
		for(int i = 1 ; i<= len1 ; i++)
			for(int j = 1; j<= len2 ; j++)
			{
			int cost = 1;
			if(word1[i-1]==word2[j-1])
				cost =0;
			f[i][j] = min(f[i-1][j-1]+cost,min(f[i][j-1]+1, f[i-1][j]+1));
			}
		return f[len1][len2];
	}
};