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][0] = i;
        for(int j = 0; j < w2Len + 1; j ++)
            editDist[0][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.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax