Contents

# Problem

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

 ``````1 2 3 4 5 6 7 `````` ``````Input: points = [[1,3],[-2,2]], K = 1 Output: [[-2,2]] Explanation: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]]. ``````

## example 2

 ``````1 2 3 4 5 6 7 8 `````` ``````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

## Dynamic programming

Main idea is 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 `````` ``````func minDistance(word1 string, word2 string) int { m:= make(map[string]int,0) return helper(word1,word2,m) } func helper(word1 string, word2 string, m map[string]int) int { k := word1+"_"+word2 if _, ok:=m[k]; ok { return m[k] } if word1==word2 { m[k] = 0 return m[k] } if len(word1) == 0 { res := len(word2) m[k]=res return res } if len(word2) == 0 { res:= len(word1) m[k]=res return res } if word1!=word2 { res := min(helper(word1[1:], word2,m),helper(word1, word2[1:],m))+1 reschanhe := min(res, helper(word1[1:], word2[1:],m)+1) m[k]=reschanhe return reschanhe } ress := helper(word1[1:],word2[1:],m) m[k] = ress return ress } func min(a,b int) int { if a