## Description

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

## Solution

``````反推：

f("horse", "ros") = 1 + min(f("hors", "ros"), // 删除 hors[e]
f("horse", "ro"), // 插入 ro[s]
f("hors", "ro"))  // 替换 hors[e] ro[s]

f("hors", "ros") = 1 + min(f("hor", "ros"), // 删除 hor[s]
f("hors", "ro"), // 插入 ro[s]
f("hor", "ro"))  // 替换 hor[s] ro[s]
...

``````

• 删除`hors[e]`：通过`f("hors", "ros")``hors`变成`ros`，则有`rose`删除最后一位得到`ros`
• 插入`ro[s]`：通过`f("horse", "ro")``horse`变成`ro`，则插入一位`s`得到`ros`
• 替换`替换 hors[e] ro[s]`：通过`f("hors", "ro")``hors`变成`ro`，则有`roe`替换最后一位得到`ros`

### 递归（Recursive）

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 `````` ``````func min(a, b int) int { if a < b { return a } return b } func min3(a, b, c int) int { return min(min(a, b), c) } func minDistance(word1, word2 string) int { w1, w2 := []byte(word1), []byte(word2) l1, l2 := len(w1), len(w2) cache := make([][]int, l1) for i := 0; i < l1; i++ { cache[i] = make([]int, l2) } var solve func(int, int) int solve = func(l1, l2 int) int { if l1 == 0 || l2 == 0 { return l1 + l2 } idx1, idx2 := l1-1, l2-1 if cache[idx1][idx2] >= 1 { // 缓存减一后返回 return cache[idx1][idx2] - 1 } var r int if w1[idx1] == w2[idx2] { // 末位相等 r = solve(l1-1, l2-1) } else { r = 1 + min3(solve(l1-1, l2), // 删除 solve(l1, l2-1), // 插入 solve(l1-1, l2-1)) // 替换 } // 避免需要初始化成`-1` // 加一后缓存 cache[idx1][idx2] = r + 1 return r } return solve(l1, l2) }``````

### 动态规划（Dynamic Programming）

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 `````` ``````func minDistance(word1 string, word2 string) int { l1, l2 := len(word1), len(word2) if l1 == 0 || l2 == 0 { return l1 + l2 } matrix := make([][]int, l1+1) for i := 0; i <= l1; i++ { matrix[i] = make([]int, l2+1) matrix[i][0] = i } for i := 0; i <= l2; i++ { matrix[0][i] = i } w1, w2 := []byte(word1), []byte(word2) for i := 1; i <= l1; i++ { for j := 1; j <= l2; j++ { if w1[i-1] == w2[j-1] { matrix[i][j] = matrix[i-1][j-1] } else { matrix[i][j] = 1 + min3(matrix[i-1][j-1], matrix[i][j-1], matrix[i-1][j]) } } } return matrix[l1][l2] }``````