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:

1. Insert a character
2. Delete a character
3. 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

dp is the edit distance of "ho" and "ro", and we can see,

1. "h" -> "r" known as dp = 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 will selecting the min among dp + 1, dp + 1, dp, 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 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;
// init dp[i], dp[j] boundary case
for (int i = 1; i < length1 + 1; i++) {
dp[i] = i;
}
for (int j = 1; j < length2 + 1; j++) {
dp[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] = i;
}
for (int j = 0; j < m + 1; j++) {
d[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

LeetCode Solution