[LeetCode] Edit Distance (Java)

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

This is a DP problem. We will use a two dimensional array distance[][] to save the edit distance. The meaning of distance[i][j] is the edit distance of substring of word1 from 0 to i, to substring of word2 from 0 to j. So, distance[0][0] is 0. And distance[0][j] will be j, because we need to insert j characters to make a empty string to a string of length j. Of course, distance[i][0] is i, because we need to delete i characters from a string of length i to a empty string.

During updating, we need to find the minimum edit distance. In fact, if the character at position i in word1 is the same as the character at position j in word2, then we know the distance[i][j] can be distance[i – 1][j – 1].Otherwise, we need a “Replace” operation, so the distance[i][j] will be distance[i – 1][j – 1] + 1. But there are some other possibilities. We can insert a character to the first string to build the second string. So the distance[i][j] can be distance[i – 1][j] + 1. Also, a removal is possible. So distance[i][j] can be distance[i + 1][j].

Since there are several options, we need to find the minimum one among them.

Code

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

public class Solution {

public int minDistance(String word1, String word2) {

int[][] distance = new int[word1.length() + 1][word2.length() + 1];

for (int i = 0; i < word1.length() + 1; i++)

for (int j = 0; j < word2.length() + 1; j++)

distance[i][j] = Integer.MAX_VALUE;

for (int i = 0; i < word2.length() + 1; i++)

distance[0][i] = i;

for (int i = 0; i < word1.length() + 1; i++)

distance[i][0] = i;

for (int i = 0; i < word1.length(); i++) {

for (int j = 0; j < word2.length(); j++) {

int min = Math.min(distance[i + 1][j], distance[i][j + 1]) + 1;

if (word1.charAt(i) == word2.charAt(j))

min = Math.min(min, distance[i][j]);

else

min = Math.min(min, distance[i][j] + 1);

distance[i + 1][j + 1] = min;

}

return distance[word1.length()][word2.length()];

}

Complexity

We need $O(mn)$ to update the distance[][] array, in which m and n are the lengths of two words. So the time complexity is $O(mn)$.