leetcode-go/hard/488.zuma-game.go

type pair struct { // The presentation of the board is the key!
	_1 rune
	_2 int
}

const INF int = 1e9

func findMinStep(board string, hand string) int {
	li := list.New()
	n := len(board)
	runes := []rune(board)
	prev := pair{runes[0], 1}
	for i := 1; i < n; i++ {
		if runes[i] == prev._1 {
			prev._2++
		} else {
			li.PushBack(prev)
			prev = pair{runes[i], 1}
		}
	}
	li.PushBack(prev)
	m := make(map[rune]int)
	for _, r := range hand {
		m[r]++
	}
	// R, Y, B, G, W
	if min := dfs(li, &m); min == INF {
		return -1
	} else {
		return min
	}
}

func dfs(li *list.List, m *map[rune]int) int {
	clearBoard(li)
	if li.Len() == 0 {
		return 0
	} else if len(*m) == 0 {
		return INF
	}
	min := INF
	for it := li.Front(); it != nil; it = it.Next() {
		p := it.Value.(pair)
		if cnt, ok := (*m)[p._1]; ok && 3 <= cnt+p._2 {
			need := 3 - p._2
			p._2 = 3
			it.Value = p
			(*m)[p._1] = cnt - need
			if cnt == need {
				delete(*m, p._1)
			}
			nli := list.New()
			nli.PushBackList(li)
			ret := dfs(nli, m) + need
			if ret < min {
				min = ret
			}
			p._2 -= need
			it.Value = p
			(*m)[p._1] = cnt
		}
	}
	return min
}

func clearBoard(li *list.List) {
	it := li.Front()
	for it != nil {
		if nxt := it.Next(); nxt != nil && nxt.Value.(pair)._1 == it.Value.(pair)._1 {
			p := pair{it.Value.(pair)._1, it.Value.(pair)._2 + nxt.Value.(pair)._2}
			it.Value = p
			li.Remove(nxt)
		} else if 3 <= it.Value.(pair)._2 {
			pre := it.Prev()
			li.Remove(it)
			if pre != nil {
				it = pre
			} else {
				it = nxt
			}
		} else {
			it = nxt
		}
	}
}