Edit distance

Post date: Sep 18, 2017 7:43:01 PM

Classic tutorial: https://web.stanford.edu/class/cs124/lec/med.pdf

use backtrace matrix to retrieve path.

My inplementation:

/*

* @param word1: A string

* @param word2: A string

* @return: The minimum number of steps.

*/

int minDistance(string &word1, string &word2) {

// write your code here

int m = word1.size();

int n = word2.size();

int distance[m+1][n+1];

// marginal distance

for (int i=0; i<=n;i++)

{

distance[0][i] = i;

}

for (int i=0; i<=m;i++)

{

distance[i][0] = i;

}

int min1,min2;

for (int i=1;i<=m;i++)

{

for (int j=1;j<=n;j++)

{

min1 = word1[i-1]==word2[j-1] ? distance[i-1][j-1]+0:distance[i-1][j-1]+1;

min2 = distance[i-1][j]<distance[i][j-1] ? distance[i-1][j]+1:distance[i][j-1]+1;

distance[i][j] = min1<min2 ? min1:min2;

}

}

return distance[m][n];

}