This solution is kind the same as the solution to LeetCode 312 Burst Balloons, but with some changes.

Chinese Version of this Post

- Step 1. Pre-process the given string as a list, which is handled by the helper function
`getBalls()`

, then we know the distribution of each color and the number of each color. - Step 2. Dynamic Programming on the pre-processed list. Unlike the solution to LeetCode 312 Burst Balloons, there are mainly 3 ways to get the optimal solution to the sub-problem.
- The first possible solution is just like the solution to LeetCode 312 Burst Balloons, we just split the given balls in 2 parts and collect the solution of each part together. The collecting operation is handled by the helper function
`combineBalls()`

- When the color of the first ball is the same as the last ball, one possible way to solve this Zuma game by finishing all balls in the middle and then take care of the first and the last balls. For example, we could solve this Zuma game
`R1 G2 R2 Y2 R1`

by finishing the part in the middle first, then care about the last`R2`

- There is also another possible way to solve this Zuma Game when the color of the first ball is the same as the last. If the number of the first ball is
`1`

or the number of the last ball is`1`

, then it is possible to combine`3`

parts together to solve the problem. For example, if the game is as`R1 G2 R1 Y2 R1`

, we could finish the`G`

part and the`Y`

part first, then go to the`R3`

part.

- The first possible solution is just like the solution to LeetCode 312 Burst Balloons, we just split the given balls in 2 parts and collect the solution of each part together. The collecting operation is handled by the helper function
- Step 3. Collect all the solution to one sub-problem, and find the solution with the fewest balls and is possible formed by the balls in our hand. Store this solution in the
`history`

for future use.

Note: For Zuma Game, if the final optimal solution can be formed by the balls in our hand, then solutions to all the optimal sub-problem can also be formed by the balls in our hand.

```
class Solution(object):
def findMinStep(self, board, hand):
"""
:type board: str
:type hand: str
:rtype: int
"""
def getBalls(balls):
"""
Convert the init given board string into a ball list.
Each element of the list is in the form of [color, ballCnt]
This function can automatically clear the 3 consective balls with
the same color in the given string.
>>> getBalls("RRBBBGYYWWWYB")
[["R", 2], ["B", 3], ["G", 1], ["B", 1]]
"""
ballList = []
for ball in balls:
if not ballList or ballList[-1][0] != ball:
if ballList and ballList[-1][1] >= 3:
ballList.pop(-1)
ballList.append([ball, 1])
elif ball == ballList[-1][0]:
ballList[-1][1] += 1
return ballList
def combineBalls(balls1, balls2):
"""
Combine 2 sets of balls together.
>>> combineBalls({"R": 1}, {"R": 1, "G": 1})
{"R": 2, "G": 1}
"""
ans = dict(balls1)
for key, value in balls2.items():
if key in ans:
ans[key] += value
else:
ans[key] = value
return ans
def cntBalls(balls):
"""
Count the number of balls we have chosen.
Since there is only 5 colors in the game, this function can be done in O(1) time.
"""
return sum(balls.values())
def updateAns(ans1, ans2):
"""
Compare two different solution to the sub-problem,
and return the better one.
If `ans1` has fewer balls and `ans1` can be formed by the balls given,
then just return `ans1`, else we return `ans2`
Therefore, `ans1` should always be the new soluton, while `ans2` the old.
"""
if cntBalls(ans1) < cntBalls(ans2) and checkAvailable(ans1, ballsInHand) >= 0:
return ans1
return ans2
def checkAvailable(balls, ballsInHand):
"""
Check whether current balls is available according to the given balls.
Since there is only 5 colors in the game, this function can be done in O(1) time.
"""
for key, value in balls.items():
if balls[key] != 0:
if key not in ballsInHand:
return -1
if ballsInHand[key] < value:
return -1
return sum(balls.values())
def memorySearch(start, end):
if end < start:
return {}
elif (start, end) in history:
return history[(start, end)]
elif start == end:
# There is only one color in the sub-problem
return {ballsTable[start][0]: 3 - ballsTable[start][1]}
elif start + 1 == end:
# There is only two color in the sub-problem
return combineBalls(memorySearch(start, start), memorySearch(end, end))
# When there are more than 3 color in the sub-problem
thisAns = {"R":float("inf")}
firstColor, lastColor = ballsTable[start][0], ballsTable[end][0]
# The first possible Solution is to split the balls into 2 parts and finish both of them seperately
for k in xrange(start, end):
thisBalls = combineBalls(memorySearch(start, k), memorySearch(k+1, end))
thisAns = updateAns(thisBalls, thisAns)
# The second possible Solution is to clear the first and the last balls in the end
if firstColor == lastColor:
toAdd = max(0, 3 - ballsTable[start][1] - ballsTable[end][1])
thisBalls = combineBalls(memorySearch(start+1, end-1), {firstColor: toAdd})
thisAns = updateAns(thisBalls, thisAns)
# The third possible Solution is to clear the first and the last balls in the end with
# one ball in the middle
if firstColor == lastColor and 1 in (ballsTable[start][1], ballsTable[end][1]):
idx = start + 1
while idx < end:
if ballsTable[idx][0] == firstColor and ballsTable[idx][1] == 1:
thisBalls = combineBalls(memorySearch(start + 1, idx - 1), memorySearch(idx + 1, end - 1))
thisAns = updateAns(thisBalls, thisAns)
idx += 1
history[(start, end)] = thisAns
return thisAns
# Initialization
ballsTable = getBalls(board)
ballsInHand = {}
for ball in hand:
ballsInHand[ball] = ballsInHand.get(ball, 0) + 1
history = {}
# print ballsTable
length = len(ballsTable)
return checkAvailable(memorySearch(0, length - 1), ballsInHand)
```