leetcode - 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

class Solution {
public:
    int minDistance(std::string word1, std::string word2) {
		int len1 = word1.size(),len2 = word2.size();
		if(len1 == 0 || len2 == 0) return std::max(len1,len2);
        std::vector<std::vector<int>> dp(len1+1,std::vector<int>(len2+1,0));
		for (int i = 0; i <= len1; i++)
		{
			dp[i][0] = i;
		}
		for (int i = 0; i <= len2; i++)
		{
			dp[0][i] = i;
		}
		for (int i = 1; i <= len1; i++)
		{
			for (int j = 1; j <= len2; j++)
			{
				if(word1[i-1] == word2[j-1])
				{
					dp[i][j] = dp[i-1][j-1];
				}
				else
				{
					dp[i][j] = std::min(dp[i-1][j-1],std::min(dp[i-1][j],dp[i][j-1])) + 1;
				}
			}
		}
		return dp[len1][len2];
    }
};

leetcode - Edit Distance

原文：http://blog.csdn.net/akibatakuya/article/details/40047135