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 n1=word1.length()+
1;
int n2=word2.length()+
1;
int min[n1][n2];
for(
int i=
0;i<n1;i++) min[i][
0]=i;
for(
int i=
0;i<n2;i++) min[
0][i]=i;
for(
int i=
1;i<n1;i++)
for(
int j=
1;j<n2;j++)
{
//replace
int min1=min[i-
1][j-
1]+(word1[i-
1]==word2[j-
1]?
0:
1);
//add or delete
int min2=min[i][j-
1]+
1;
int min3=min[i-
1][j]+
1;
if(min1>min2) min1=min2;
if(min1>min3) min1=min3;
min[i][j]=min1;
}
return min[n1-
1][n2-
1];
}
};
Edit Distance,布布扣,bubuko.com
Edit Distance
原文：http://www.cnblogs.com/erictanghu/p/3759480.html
