[Leetcode] 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

Analysis:

Let f[i][j] be the minimum number of steps required to convert word1 of size i to word2 of size j. The last character of word1 may or may not be equal to the one of word2. 

Case1: considering word1 (Xa) and word2 (Ya). Since the last character of word1 is equal to the last character of word2, deleting the last character of both would not change the steps converting word1 to word2, that is, f[i][j] = f[i-1][j-1].

Case 2: Considering word1 (Xa) and word2 (Yb). Since last character of word1 is NOT equal to the last character of word2, to convert word1 to word2, there are 3 ways to convert word1 to word2 and the minimum one is the one we wanted:

• Replace the character a with b of word1, so that word1(Xb) and word2(Yb). so the steps will become f[i][j] = f[i-1][j-1] + 1
• Insert character b to word1, so that word1(Xab) and word2(Yb) and according to case1, so deleting b would make the steps become f[i][j] = f[i][j-1] + 1
• Insert character a to word2, so that word1(Xb) and word2(Yba) and according to case1, so deleting a would make the steps become f[i][j] = f[i-1][j] + 1

We have f[i][j] = min(min(f[i][j-1], min(f[i-1][j]), f[i-1][j-1])

If word1 is empty, f[0][j] = j and if word2 is empty, f[i][0] = i

Given the above equation, it is pretty easy to have the code.  

    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int> > f(m+1, vector<int>(n+1, 0));
        for(int i=0; i<=m; i++)
        {
            for(int j=0; j<=n; j++)
            {
                if (i == 0)
                    f[i][j] = j;
                else if (j == 0)
                    f[i][j] = i;
                else
                {
                    if (word1[i-1] == word2[j-1])
                        f[i][j] = f[i-1][j-1];
                    else
                        f[i][j] = min(min(f[i][j-1], f[i-1][j]), f[i-1][j-1]) + 1;
                }
            }
        }
        
        return f[m][n];
        
    }