Edit Distance
Given two wordsword1_and_word2, find the minimum number of operations required to convertword1_to_word2.
You have the following 3 operations permitted on a word:
Insert a character
Delete a character
Replace a character
Example 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Example 2:
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')
Analysis
The best way to think of the DP solution of this problem is to visualize it:
dp[i][j]
- stands for edit distance between substring [0, i] of word1and substring [0, j] of word2
Thus dp[M][N]
will be the result, where M
is the length of (rows), and N
is the length of word2 (columns)
For example:
| h o r s e | vs | r o s |
Diagram:
Since three types edit are allowed: Insert (I), Replace (R), Delete (R), showing each type of edit operation in the diagram for dp[2][2]
dp[2][2]
is the edit distance of "ho" and "ro", and we can see,
1. "h" -> "r" known as dp[1][1]
= 1,
2. or "ho" to "r" first, then "r" Insert "o"
3. or "h" to "ro" first, then "h" Insert "o"
then "ho" -> "ro", since the "o" is same for "ho" and "ro", then dp[2][2] will selecting the min among dp[1][2] + 1
, dp[2][1] + 1
, dp[1][1]
, which is 1
In short, the state transfer function would be
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1] - 1);
} else {
dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
}
Also, the official solution is great: https://leetcode.com/problems/edit-distance/solution/
Note: dp[i][j]
2D array was initialized with word length + 1, since it's accounting for dp[0][0]
would be empty string to empty string edit, also dp[M][N]
will be the final result.
Thus when comparing, check word1.charAt(i - 1)
, word2.charAt(j - 1)
, since the index i, j means the i-th
, j-th
character instead of index in the string.
Solution
DP Solution - O(mn) space, O(mn) time
class Solution {
public int minDistance(String word1, String word2) {
int length1 = word1.length();
int length2 = word2.length();
if (length1 * length2 == 0) return length1 + length2;
// dp[i][j] - edit distance for (0, i) of word1 to (0, j) word2
int[][] dp = new int[length1 + 1][length2 + 1];
// initialization
// assuming '*' to '*' for (0, 0) case
dp[0][0] = 0;
// init dp[i][0], dp[0][j] boundary case
for (int i = 1; i < length1 + 1; i++) {
dp[i][0] = i;
}
for (int j = 1; j < length2 + 1; j++) {
dp[0][j] = j;
}
for (int i = 1; i < length1 + 1; i++) {
for (int j = 1; j < length2 + 1; j++) {
// edit distance coming from up, left, up-left
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1] - 1);
} else {
dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
}
}
}
return dp[length1][length2];
}
}
DP - Official Solution
class Solution {
public int minDistance(String word1, String word2) {
int n = word1.length();
int m = word2.length();
// if one of the strings is empty
if (n * m == 0)
return n + m;
// array to store the convertion history
int [][] d = new int[n + 1][m + 1];
// init boundaries
for (int i = 0; i < n + 1; i++) {
d[i][0] = i;
}
for (int j = 0; j < m + 1; j++) {
d[0][j] = j;
}
// DP compute
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < m + 1; j++) {
int left = d[i - 1][j] + 1;
int down = d[i][j - 1] + 1;
int left_down = d[i - 1][j - 1];
if (word1.charAt(i - 1) != word2.charAt(j - 1))
left_down += 1;
d[i][j] = Math.min(left, Math.min(down, left_down));
}
}
return d[n][m];
}
}
Reference
Minimum Edit Distance - Stanford Computational Biology Slides & Video
Last updated
Was this helpful?