-
Notifications
You must be signed in to change notification settings - Fork 514
/
d.go
60 lines (57 loc) · 1.04 KB
/
d.go
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
54
55
56
57
58
59
60
package main
func isSolvable(words []string, result string) bool {
indexMap := func(s string) map[byte]int {
mp := map[byte]int{}
id := 0
for i := range s {
b := s[i]
if _, ok := mp[b]; !ok {
mp[b] = id
id++
}
}
return mp
}
allS := result
for _, word := range words {
allS += word
}
idMap := indexMap(allS)
n := len(idMap)
var canZero, used [10]bool
var weights [10]int
calcWeight := func(s string, sign int) {
w := 1
for i := len(s) - 1; i >= 0; i-- {
weights[idMap[s[i]]] += w * sign
w *= 10
}
}
for i := range canZero {
canZero[i] = true
}
for _, w := range words {
canZero[idMap[w[0]]] = false
calcWeight(w, 1)
}
canZero[idMap[result[0]]] = false
calcWeight(result, -1)
var f func(int, int) bool
f = func(cur, sum int) bool {
if cur == n {
return sum == 0
}
for i := 0; i < 10; i++ {
if i == 0 && !canZero[cur] || used[i] {
continue
}
used[i] = true
if f(cur+1, sum+i*weights[cur]) {
return true
}
used[i] = false
}
return false
}
return f(0, 0)
}