# 一起刷leetcode(72):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

/*--------------------------
* Date:2015-03-07
* Author:qingyuanxingsi
* Title:72.Edit Distance
* Result:AC
* Idea:DP
*/
include <iostream>using namespace std;

class Solution {
public:
int minDistance(string word1, string word2) {
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] = i;
}
for(int j=0;j<size2+1;j++){
distance[j] = j;
}
for(int i=0;i<size1;i++){
for(int j=0;j<size2;j++){
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可以快速收藏哦~

• APP下载 七月在线APP
• 微信公众号 扫码免费领课
• 返回顶部