# DP O(N^3) Solution in Python with explanation

• 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.
• 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)
``````

• Though, after submitting, this solution takes 89 ms to finish all the test cases, which is little slower than the normal DFS solution.
My solution can run the test case below in 539 ms, while `Expected Answer` didn't show any expected answer.
`"WWYRBGGWYRGBBWYRYGBRYWGBRYWGGRYWBGBGRWYYGBRYWYGBRYWGBYRRGBYWYRYGBRYYGYRBWYRYGBBGGRYWBWBYRYBGYRWYBGYR"`
`"WWWWWWWWWWWWWWWWWWWWWWWWWWRRRRRRRRRRRRRRRRRRRRRRRRRRRRGGGGGGGGGGGGGGGGGGGGGGGYYYYYYYYYYYYYYYBBBBBBBBBBBBBBBBBBBBB"`
This means the test case is kinda friendly to the DFS solution.

Can anyone tell me whether my solution is correct or not when the input is large?

• Your Solution fails on this test case:
"GRWWRBBRYYRG"
"RGBYW"

• No, i don't think DP will work.

In your DP solution, you cannot just save ONE answer to each sub-problem in the DP table (or history[] in your python code). What if there's a tie when you compare two answer by updateAns(ans1, ans2)? For example, let's say there's four ball on the board as a sub-problem:
RWRW
you can clear the board with either 1W4R or 4W1R. You cannot tell which is better, or feasible, until you see the other part of the whole board.

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.