Given two words

word1andword2, find the minimum number of steps required to convertword1toword2. (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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
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)$.