# LC 72 Edit distance

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

We can either insert, delete or replace There are 4 scenarios here:

# No change from previous edit distance

edit-dist(‘abcd’, ‘aeed’) = edit-dist(‘abc’, ‘aee’) because the last char match. If we can find edit-dist(‘abc’, ‘aee’) and find a transformation from ‘abc’ to ‘aee’, we don’t need to edit anything to extend to ‘abcd’ and ‘aeed’.

# Replace

If we try to find out edit-dist(‘deny’, ‘eph’), we notice that their last char don’t match. If we find edit-dist(‘den’, ‘ep’), string1 becomes ‘epy’. We know need to replace y with h. and it takes 1 steps

# delete

edit-dist(‘deny’, ‘eph’). If we find edit-dist(‘den’, ‘eph’), then string1 = ‘ephy’. We need to delete the last y to let string1 = string2.

# append

edit-dist(‘deny’, ‘eph’). If we find edit-dist(‘eph’, ‘den’) then string2 = den, we need to append a y to string 2 to let string1=string2.

We notice that delete is kinda reverse of append.

``````    int minDistance(string word1, string word2) {
int w1Len = word1.size();
int w2Len = word2.size();
std::vector<std::vector<int>> editDist(w1Len + 1, std::vector<int>(w2Len + 1, 0));
for(int i = 0; i < w1Len + 1; i ++)
editDist[i] = i;
for(int j = 0; j < w2Len + 1; j ++)
editDist[j] = j;

for (int i = 1; i < w1Len + 1; i ++){
for(int j = 1; j < w2Len + 1; j ++){
if (word1[i - 1] == word2[j - 1])
editDist[i][j] =  editDist[i - 1][j - 1];
else{
editDist[i][j] = 1 + min(editDist[i - 1][j],
min(editDist[i][j - 1],
editDist[i - 1][j - 1]));
}
}
}
return editDist[w1Len][w2Len];
}

#Bugs
I used to have
if (word1[i - 1] == word2[j - 1])!!
It will always have memory error because the information stored at editDist[i][j] is the edit distance between word1[:i - 1] and word2[: j - 1]. Because the empty string takes up space.

``````