We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Zuma Game

Difficulty: Hard

Problem Description

In a variation of the game Zuma, you have a row of colored balls on a board and several colored balls in your hand. Your goal is to clear all the balls from the board by inserting balls from your hand. If inserting a ball creates a group of three or more consecutive balls of the same color, that group is removed. You need to return the minimum number of balls you have to insert to clear all the balls from the board, or -1 if it is impossible.

Key Insights

  • You can insert any ball from your hand at any position on the board.
  • Groups of three or more consecutive balls of the same color will be removed.
  • The removal process can trigger subsequent removals, so this must be handled recursively.
  • A depth-first search (DFS) approach can be used to explore all possible insertions and their effects on the board.
  • Memoization can optimize the DFS by storing results of already computed board and hand states.

Space and Time Complexity

Time Complexity: O(N^2 * M), where N is the length of the board and M is the length of the hand. Space Complexity: O(N), for storing the state of the board during recursive calls.

Solution

The solution utilizes depth-first search (DFS) to explore the possible ways to insert balls from the hand into the board. Each time a ball is inserted, we need to check if it causes any groups to be formed and subsequently removed. This process can be recursive, and memoization is employed to avoid recalculating results for the same state (board and hand). The algorithm keeps track of the minimum number of balls inserted that lead to clearing the board.

Code Solutions

def findMinStep(board: str, hand: str) -> int:
    from collections import Counter

    def remove_consecutive_balls(board):
        stack = []
        for ball in board:
            if stack and stack[-1] == ball:
                count = 1
                while stack and stack[-1] == ball:
                    stack.pop()
                    count += 1
                if count < 3:
                    stack.extend([ball] * count)
            else:
                stack.append(ball)
        return ''.join(stack)

    def dfs(board, hand_count):
        board = remove_consecutive_balls(board)
        if not board:
            return 0
        if not hand_count:
            return float('inf')

        min_steps = float('inf')
        for i in range(len(board) + 1):
            for ball in hand_count:
                if hand_count[ball] > 0:
                    next_board = board[:i] + ball + board[i:]
                    next_hand_count = hand_count.copy()
                    next_hand_count[ball] -= 1
                    steps = dfs(next_board, next_hand_count)
                    if steps != float('inf'):
                        min_steps = min(min_steps, steps + 1)

        return min_steps

    hand_count = Counter(hand)
    result = dfs(board, hand_count)
    return result if result != float('inf') else -1
← Back to All Questions