[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


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.



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)$.