Edit Distances

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

DP solution: see explantation - http://en.wikipedia.org/wiki/Edit_distance

• ab, ac -> replace b with c
• a, ac -> insert c after a
• ac, a -> delete c after a

Since we only need current and previous results, we can optimize the space by using 2 rows matrix.

public int minDistance(String word1, String word2) {
        int[][] distances = new int[word1.length()+1][word2.length()+1];

        for (int i=0; i<distances.length; i++) {
            distances[i][0] = i;
        }

        for (int j=0; j<distances[0].length; j++) {
            distances[0][j] = j;
        }

        for (int i=1; i<=word1.length(); i++) {
            char w1 = word1.charAt(i-1);
            for (int j=1; j<=word2.length(); j++) {
                char w2 = word2.charAt(j-1);
                if (w1==w2) {
                    distances[i][j] = distances[i-1][j-1];
                } else {
                    int insert = distances[i][j-1] + 1;
                    int replace = distances[i-1][j-1] + 1;
                    int delete = distances[i-1][j] + 1;
                    distances[i][j] = Math.min(insert, Math.min(replace, delete));
                }
            }
        }

        return distances[word1.length()][word2.length()];
     }

Trie solution (to be added)