488. Zuma Game
对每一个s消除三个连续的球，然后对于每一个可以消除的位置进行搜索，取其最小值。这道题的解法和思路比较复杂，但是也比较清晰，值得再写一遍。
class Solution(object):
def findMinStep(self, board, hand):
"""
:type board: str
:type hand: str
:rtype: int
"""
self.MAXCOUNT = 6
handCount = [0] * 26
for c in hand:
handCount[ord(c) - ord('A')] += 1
res = self.helper(board + "#", handCount); #append a "#" to avoid special process while j==board.length, make the code shorter.
return -1 if res == self.MAXCOUNT else res
def helper(self, s, h):
s = self.removeConsecutive(s)
if s == "#":
return 0
res = self.MAXCOUNT
need = 0
i = 0
for j in range(len(s)):
if s[i] == s[j]:
continue
need = 3 - (j - i) #balls need to remove current consecutive balls.
if h[ord(s[i]) - ord('A')] >= need:
h[ord(s[i]) - ord('A')] -= need
res = min(res, need + self.helper(s[0:i] + s[j:], h))
h[ord(s[i]) - ord('A')] += need
i = j
return res
#remove consecutive balls longer than 3
def removeConsecutive(self, board):
i = 0
for j in range(len(board)):
if board[i] == board[j]:
continue
if j - i >= 3:
return self.removeConsecutive(board[0:i] + board[j:])
else:
i = j
return board
