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[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
}
|