# Edit Distance

Given two words

*word1_and_word2*, find the minimum number of operations required to convert*word1_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')

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 word2Thus

`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 1In 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]);

}

**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.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];

}

}

Last modified 3yr ago