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

Solution:

Assume that the total number of operations is d. Pick letters from both strings: x1 and x2. If x1 = x2, remove both and pick next letters.

If they are different, compare three operations:
a) insert a character, i.e., remove x2 from word2 since we will insert x2 to word1. Then pick letters from word1 and word2 again.
b) delete a character, i.e., remove x1 from word1.
c) replace a character, i.e., remove both x1 and x2.
All these cases we need one extra operation.

So the recursion is:
s1 = delete the first character of word1
s2 = delete the first character of word2
d(word1, word2) = d(s1, s2), if the first characters are the same.
d(word1, word2) = 1 + min(d(s1, word2), d(word1, s2), d(s1, s2))

The following recursive version only passes the LeetCode OJ small judge.

class Solution {
public:
    int minDistance(string word1, string word2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int d = helper(word1, word2);
        return d;
    }
    int helper(string word1, string word2) {
        int len1 = word1.size(), len2 = word2.size();
        if (len1 == 0 || len2 == 0) return abs(len2 - len1);
        string s1 = word1.substr(1, len1 - 1);
        string s2 = word2.substr(1, len2 - 1);
        if (word1[0] != word2[0]) {
            return 1 + min(helper(s1, s2),
            min(helper(s1, word2), helper(word1, s2)));
        }
        else {
            return helper(s1, s2);
        }
    }
};

It is easy to convert this to dynamic programming solution. Use a two dimensional array to store the distance d(i, j).
The following code passes the LeetCode OJ Large Judge.

class Solution {
public:
    int minDistance(string word1, string word2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int len1 = word1.size(), len2 = word2.size();
        if (len1 == 0 || len2 == 0) return abs(len2 - len1);
        int dist[len1][len2];
        dist[0][0] = (word1[0] == word2[0]) ? 0 : 1;
        for (int i = 1; i < len1; i++) {
            dist[i][0] = (word1[i] == word2[0]) ? i : dist[i-1][0]+1;
        }
        for (int j = 1; j < len2; j++) {
            dist[0][j] = (word1[0] == word2[j]) ? j : dist[0][j-1]+1;
        }
        for (int i = 1; i < len1; i++) {
            for (int j = 1; j < len2; j++) {
                if (word1[i] == word2[j])
                    dist[i][j] = dist[i-1][j-1];
                else
                    dist[i][j] = 1 +
                    min(min(dist[i-1][j], dist[i][j-1]), dist[i-1][j-1]);
            }
        }
        return dist[len1-1][len2-1];
    }
};