forked from wufenggirl/LeetCode-in-Golang
-
Notifications
You must be signed in to change notification settings - Fork 0
/
zuma-game.go
executable file
·61 lines (53 loc) · 1008 Bytes
/
zuma-game.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
61
package problem0488
var maxCount = 6
func findMinStep(board, hand string) int {
// ball[i] = j 表示, 手上拥有 i+'A' 颜色的球的个数
ball := make([]int, 26)
for i := 0; i < len(hand); i++ {
ball[hand[i]-'A']++
}
res := dfs(board+"#", ball)
if res == maxCount {
return -1
}
return res
}
func dfs(s string, ball []int) int {
s = removeBalls(s)
if s == "#" {
return 0
}
res, need := maxCount, 0
for i, j := 0, 0; j < len(s); j++ {
if s[j] == s[i] {
continue
}
need = 3 - (j - i)
if ball[s[i]-'A'] >= need {
ball[s[i]-'A'] -= need
res = min(res, need+dfs(s[:i]+s[j:], ball))
ball[s[i]-'A'] += need
}
i = j
}
return res
}
// 删除 board 中 3 个及以上同色的球
func removeBalls(board string) string {
for i, j := 0, 0; j < len(board); j++ {
if board[i] == board[j] {
continue
}
if i+3 <= j {
return removeBalls(board[:i] + board[j:])
}
i = j
}
return board
}
func min(a, b int) int {
if a < b {
return a
}
return b
}