# 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')
```

## 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:\
![edit\_distance\_diagram](https://1611446478-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M63nDeIUEfibnkE8C6W%2Fsync%2F72cbe7835c78c7f4926f4381826919a732371df1.png?generation=1588144785332046\&alt=media)

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

```java
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

```java
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](https://web.stanford.edu/class/cs124/lec/med.pdf) - Stanford Computational Biology Slides & [Video](https://www.youtube.com/watch?v=Xxx0b7djCrs)

[LeetCode Solution](https://leetcode.com/problems/edit-distance/solution/)