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:

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

## Solution

Use `dynamic programming`

**Base case:** Convert a `n`

length string to an `empty`

string needs `n`

operations

**General case:**

If `dp[i-1][j-1]`

is minimum operations count to convert `i-1`

length string to `j-1`

length string, then

- When next characters are same, minimum operations will not be changed,

`dp[i][j] = dp[i-1][j-1]`

- When next characters are not same, there're more 3 cases to consider

+ Insert:`dp[i][j] = dp[i][j - 1] + 1`

+ Replace:`dp[i][j] = dp[i - 1][j - 1] + 1`

+ Delete:`dp[i][j] = dp[i - 1][j] + 1`

Let's code!

```
class Solution {
func minDistance(_ word1: String, _ word2: String) -> Int {
if word1 == "" { return word2.count }
if word2 == "" { return word1.count }
let word1 = Array(word1)
let word2 = Array(word2)
let m = word1.count
let n = word2.count
var dp = [[Int]](repeating: [Int](repeating: 0, count: n + 1), count: m + 1)
for i in 1...m {
dp[i][0] = i
}
for j in 1...n {
dp[0][j] = j
}
for i in 1...m {
for j in 1...n {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1]
} else {
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1
}
}
}
return dp[m][n]
}
}
```