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


  • 2

    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)
    

  • 0

    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?


  • 1
    S

    Your Solution fails on this test case:
    "GRWWRBBRYYRG"
    "RGBYW"
    The answer should be 5, but your code returns -1.


  • 0
    L

    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.


  • 0
    L
    This post is deleted!

Log in to reply
 

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