一起刷leetcode(72):Edit Distance


问题:72.Edit Distance
链接:https://oj.leetcode.com/problems/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
已邀请:

青原行思 - Crazy about ML!

赞同来自: jefflee


经典DP问题,已AC.
/*--------------------------
* Date:2015-03-07
* Author:qingyuanxingsi
* Title:72.Edit Distance
* Link:https://oj.leetcode.com/problems/edit-distance/
* Result:AC
* Idea:DP
*/

include <iostream>

using namespace std;

class Solution {
public:
    int minDistance(string word1, string word2) {
        const int add_cost =1,delete_cost=1,replace_cost=1;
        const int size1 = word1.size();
        const int size2 = word2.size();
        int distance[size1+1][size2+1];
        for(int i=0;i<size1+1;i++){
            distance[i][0] = i;
        }
        for(int j=0;j<size2+1;j++){
            distance[0][j] = j;
        }
        for(int i=0;i<size1;i++){
            for(int j=0;j<size2;j++){
                int temp = get_min(distance[i][j+1]+delete_cost,distance[i+1][j]+add_cost);
                if(word1[i]==word2[j]){
                    distance[i+1][j+1] = get_min(distance[i][j],temp);
                }
                else{
                    distance[i+1][j+1] = get_min(distance[i][j]+replace_cost,temp);
                }
            }
        }
        return distance[size1][size2];
    }

    inline int get_min(const int a,const int b){
        return a<b?a:b;
    }
};

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~