Dynamic programing for edit distance (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

Thoughts:
First, we explain the recursive structure here. Denote ed(s_{1}, s_{2}) as the edit distance between s_{1} and s_{2}. For base case, we have:

  • ed('', '') = 0
  • ed('', s) = ed(s, '') = \|s\|

Then, for the recursive step, we have:

  • ed(s_{1}+ch1, s_{2}+ch2) = ed(s_{1}, s_{2}) if ch1 == ch2 since we don’t need to anything from s_{1},s_{2} to s_{1}+ch1, s_{2}+ch2.
  • ed(s_{1}+ch1, s_{2}+ch2) = \min(1 + ed(s_{1}, s_{2}), 1 + ed(s_{1}+ch1, s_{2}), 1 + ed(s_{1}, s_{2}+ch2)) if ch1 != ch2. Here we compare three options:
    1. Replace ch1 with ch2, hence 1 + ed(s_{1}, s_{2}).
    2. Insert ch2 into s_{2}, hence 1 + ed(s_{1}+ch1, s_{2}).
    3. Delete ch1 from s_{1}, hence 1 + ed(s_{1}, s_{2}+ch2).

Code (Java):

public class Solution {
    public int minDistance(String word1, String word2) {
        int[][] table = new int[word1.length()+1][word2.length()+1];
        for(int i = 0; i < table.length; ++i) {
            for(int j = 0; j < table[i].length; ++j) {
                if(i == 0)
                    table[i][j] = j;
                else if(j == 0)
                    table[i][j] = i;
                else {
                    if(word1.charAt(i-1) == word2.charAt(j-1))
                        table[i][j] = table[i-1][j-1];
                    else
                        table[i][j] = 1 + Math.min(Math.min(table[i-1][j-1], 
                            table[i-1][j]), table[i][j-1]);
                }
            }
        }
        return table[word1.length()][word2.length()];
    }
}

Code (C++):

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int> > table(word1.size()+1, vector<int>(word2.size()+1));
        for(int i = 0; i < word1.size()+1; ++i) {
            for(int j = 0; j < word2.size()+1; ++j) {
                if(i == 0)
                    table[i][j] = j;
                else if(j == 0)
                    table[i][j] = i;
                else {
                    if(word1[i-1] == word2[j-1])
                        table[i][j] = table[i-1][j-1];
                    else
                        table[i][j] = min(min(1+table[i-1][j-1],
                                1+table[i-1][j]), 1+table[i][j-1]);
                }
            }
        }
        return table[word1.size()][word2.size()];
    }
};
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: