首页 > 其他 > 详细

Edit Distance

时间:2014-12-03 22:40:56      阅读:288      评论:0      收藏:0      [点我收藏+]

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(string word1, string word2) {
        int l1 = word2.length();
        int l2 = word1.length();
        vector<vector<int> > dp;
        for(int i=0; i<=l1; i++){
            vector<int> tmp(l2+1, 0);
            dp.push_back(tmp);
        }
        for(int i=0;i<=l1;i++){
            dp[i][0] = i;
        }
        for(int i=0;i<=l2;i++){
            dp[0][i] = i;
        }
        int a, b;
        for(int i=1;i<=l1;i++){
            for(int j=1;j<=l2;j++){
                a = (word2[i-1] == word1[j-1]) ? dp[i-1][j-1] : (dp[i-1][j-1]+1);
                b = min(dp[i-1][j],dp[i][j-1]) + 1;
                dp[i][j] = min(a, b);
            }
        }
        return dp[l1][l2];
    }
};

 

Edit Distance

原文:http://www.cnblogs.com/code-swan/p/4141219.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!