编程之美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

dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1

class Solution {
public:
    int minDistance(string word1, string word2) {
    	int length1 = word1.size(),length2 = word2.size(),i,j;
    	vector<vector<int> > dp(length1+1);
    	for(i = 0;i <= length1;++i)
    	{
    		vector<int> tmp(length2+1,0);
    		dp[i] = tmp;
    	}
    	for(i = 1; i <= length1;++i)dp[i][0] = i;
    	for(j = 1; j <= length2;++j)dp[0][j] = j;
    	for(i = 1; i <= length1;++i)
    	{
    		for(j = 1;j <= length2;++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],min(dp[i-1][j],dp[i][j-1]))+1;
    		}
    	}
    	return dp[length1][length2];
    }
};

编程之美leetcode之编辑距离,布布扣,bubuko.com

编程之美leetcode之编辑距离

原文：http://blog.csdn.net/fangjian1204/article/details/38664659