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

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

 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[0]!=word2[0] {
        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<b {
        return a
    }
    return b
}