LeetCode 488: Zuma Game Solution in Python – A Step-by-Step Guide

What Is LeetCode 488: Zuma Game?

In LeetCode 488: Zuma Game, you’re given two strings: board (the initial sequence of colored balls) and hand (the balls you can use), and your task is to find the minimum number of balls from hand needed to clear board. You can insert a ball from hand at any position in board, and if a group of three or more consecutive balls of the same color forms, it’s removed, potentially triggering more eliminations. Return this minimum number, or -1 if impossible. For example, with board = "WRRBBW" and hand = "RB", you need at least 2 balls (e.g., "BB" to clear it), while board = "WWRRBBWW" with hand = "WR" needs 2. It’s like playing a real-time Zuma match, strategizing each shot to zap the board clean.

Problem Statement

• Input: board (str)—initial board; hand (str)—available balls.
• Output: int—minimum balls to clear board, or -1 if impossible.
• Rules:
• Insert one ball from hand at any position in board.
• Remove groups of 3+ consecutive same-color balls, repeat until no more eliminations.
• Use only balls from hand, minimize count.

Constraints

• \( 1 \leq board.length \leq 16 \).
• \( 1 \leq hand.length \leq 5 \).
• Both strings contain only 'R', 'W', 'B', 'G', 'Y' (red, white, blue, green, yellow).

Examples to Get Us Started

• Input: board = "WRRBBW", hand = "RB"
• Output: 2 (Insert "BB" at end: "WRRBBWBB" → "W", 2 balls used).
• Input: board = "WWRRBBWW", hand = "WR"
• Output: 2 (Insert "W" and "R" strategically: "WWRRBBWW" → clear, 2 balls).
• Input: board = "G", hand = "GGGGG"
• Output: 2 (Insert 2 "G"s: "GGG" → clear).

Understanding the Problem: Clearing the Board

To solve LeetCode 488: Zuma Game in Python, we need to determine the minimum number of balls from hand to insert into board to eliminate all balls, where inserting a ball can trigger consecutive groups of 3+ to vanish, repeating until stable. A naive approach—trying all possible insertions recursively—could be O(5^n * n) (5 hand choices, n positions), infeasible for board length 16 and hand size 5. The key? Use DFS with memoization and pruning to explore optimal insertions efficiently, leveraging the small constraint sizes. We’ll explore:

• Best Solution (DFS with Memoization and Pruning): O(n * 5^m * n) time, O(n * 5^m) space—fast and optimal (n = board length, m = hand length).
• Alternative Solution (Brute Force DFS): O(5^n * n) time, O(n)—simple but slow.

Let’s dive into the memoized DFS solution—it’s the Zuma master’s sharpshooter we need.

Best Solution: DFS with Memoization and Pruning

Why This Is the Best Solution

The DFS with memoization and pruning is the top pick because it’s O(n * 5^m * n) time (n = board length, m = hand length) and O(n * 5^m) space, efficiently finding the minimum balls by exploring insertion possibilities with a depth-first search, caching results to avoid redundant calculations, and pruning invalid paths early. It compresses the board after each elimination, reducing complexity. It’s like aiming each shot with a playbook, recalling past moves and skipping dead ends—smart and precise!

How It Works

Here’s the strategy:

• Step 1: Define helper to clean board:
• Remove groups of 3+ consecutive same-color balls, repeat until stable.
• Step 2: DFS with memoization:
• \( dfs(board, hand) \) = min balls to clear board with given hand.
• Key: (board, hand tuple).
• Base: board empty → 0, hand empty but board not → inf.
• Step 3: For each position i in board and ball c in hand:
• Insert c at i, clean board, recurse with updated hand.
• Prune if insertion doesn’t help (e.g., no 2+ group possible).
• Step 4: Return min balls or -1 if inf.
• Why It Works:
• Memoization caches subproblems (board, hand states).
• Cleaning optimizes board size per step.

Step-by-Step Example

Example: board = "WRRBBW", hand = "RB"

• Init: \( dfs("WRRBBW", "RB") \).
• Insert R at 0: "RWRRBBW" → "WBBW" (RRR gone), \( dfs("WBBW", "B") \):
• Insert B at 2: "WBBB" → "", \( dfs("", "") = 0 \), total = 2.
• Insert B at 4: "WRRBBB" → "W", \( dfs("W", "R") = 2 \) (needs 2 more), total = 3.
• Min: 2 (path: "WRRBBW" → "WBBW" → "").
• Result: 2.

Example: board = "G", hand = "GGGGG"

• Insert G at 0: "GG" → \( dfs("GG", "GGGG") \):
• Insert G: "GGG" → "", \( dfs("", "GGG") = 0 \), total = 2.
• Result: 2.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        def clean_board(board):
            while True:
                new_board = ""
                i = 0
                while i < len(board):
                    j = i
                    while j < len(board) and board[j] == board[i]:
                        j += 1
                    if j - i >= 3:
                        i = j  # Skip group
                    else:
                        new_board += board[i:j]
                        i = j
                if new_board == board:
                    break
                board = new_board
            return board

        # Memoization cache
        memo = {}

        def dfs(board: str, hand: str) -> int:
            if not board:
                return 0  # Board cleared
            if not hand:
                return float('inf')  # No balls, board remains

            state = (board, hand)
            if state in memo:
                return memo[state]

            min_steps = float('inf')
            hand_count = {}
            for c in hand:
                hand_count[c] = hand_count.get(c, 0) + 1

            # Try inserting each ball at each position
            for i in range(len(board) + 1):
                for c, count in hand_count.items():
                    if count == 0:
                        continue
                    # Prune: only insert where it can form 2+ with neighbors
                    if (i > 0 and board[i-1] == c) or (i < len(board) and board[i] == c):
                        new_board = board[:i] + c + board[i:]
                        new_board = clean_board(new_board)
                        new_hand = hand.replace(c, '', 1)
                        steps = dfs(new_board, new_hand)
                        if steps != float('inf'):
                            min_steps = min(min_steps, 1 + steps)

            memo[state] = min_steps if min_steps != float('inf') else float('inf')
            return memo[state]

        # Main call
        result = dfs(board, hand)
        return result if result != float('inf') else -1

• Line 3-18: clean_board: Remove 3+ groups iteratively.
• Line 21: Memo cache for (board, hand) states.
• Line 23-49: DFS:
• Base: empty board = 0, no hand = inf.
• Count hand balls, try each insertion.
• Prune: insert only where c can form 2+ with neighbors.
• Clean board, recurse, track min steps.
• Line 52-54: Return result or -1 if impossible.
• Time Complexity: O(n * 5^m * n)—n positions, 5^m hand states, n for cleaning.
• Space Complexity: O(n * 5^m)—memo size.

It’s like a Zuma sharpshooter!

Alternative Solution: Brute Force DFS

Why an Alternative Approach?

The brute force DFS—O(5^n * n) time, O(n) space—tries all possible insertions without memoization, computing min balls by exhaustively exploring each move. It’s slow but intuitive, like shooting every ball everywhere to see what sticks. Good for small cases or learning!

How It Works

• Step 1: DFS without memo:
• Try each ball at each position, clean, recurse.
• Step 2: Base: empty board = 0, no hand = inf.
• Step 3: Return min steps or inf.
• Step 4: Adjust to -1 if impossible.

Step-by-Step Example

Example: board = "WRRBBW", hand = "RB"

• Insert R at 0: "RWRRBBW" → "WBBW", \( dfs("WBBW", "B") = 1 \), total = 2.
• Insert B at 4: "WRRBBB" → "W", \( dfs("W", "R") = 2 \), total = 3.
• Min: 2.
• Result: 2.

Code for Brute Force

Copy codeclass Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        def clean_board(board):
            # Same as above, simplified
            while "RRR" in board or "WWW" in board or "BBB" in board or "GGG" in board or "YYY" in board:
                i = 0
                while i < len(board):
                    j = i
                    while j < len(board) and board[j] == board[i]:
                        j += 1
                    if j - i >= 3:
                        board = board[:i] + board[j:]
                        break
                    i = j
            return board

        def dfs(board: str, hand: str) -> int:
            if not board:
                return 0
            if not hand:
                return float('inf')

            min_steps = float('inf')
            for i in range(len(board) + 1):
                for c in hand:
                    new_board = board[:i] + c + board[i:]
                    new_board = clean_board(new_board)
                    new_hand = hand.replace(c, '', 1)
                    steps = dfs(new_board, new_hand)
                    if steps != float('inf'):
                        min_steps = min(min_steps, 1 + steps)

            return min_steps

        result = dfs(board, hand)
        return result if result != float('inf') else -1

• Line 3-14: Simplified clean_board.
• Line 16-31: Brute force DFS, no memo.
• Time Complexity: O(5^n * n)—exponential insertions.
• Space Complexity: O(n)—recursion stack.

It’s a slow Zuma blaster!

Comparing the Two Solutions

• DFS with Memoization (Best):
• Pros: O(n * 5^m * n), fast, scalable.
• Cons: O(n * 5^m) space.
• Brute Force (Alternative):
• Pros: O(5^n * n), simple.
• Cons: Impractical for large inputs.

Memoized DFS wins for efficiency.

Edge Cases and Examples

• Input: board="RR", hand="R" → 1.
• Input: board="R", hand="" → -1.
• Input: board="WWW", hand="W" → 1.

Memoized DFS handles all well.

Complexity Recap

• Memoized DFS: Time O(n * 5^m * n), Space O(n * 5^m).
• Brute Force: Time O(5^n * n), Space O(n).

Memoized DFS is the champ.

Key Takeaways

• Memoized DFS: Optimize with memory.
• Brute Force: Blast all moves.
• Python Tip: Memo speeds—see [Python Basics](/python/basics).

Final Thoughts: Clear That Board

LeetCode 488: Zuma Game in Python is a colorful strategy challenge. Memoized DFS with pruning is your fast sharpshooter, while brute force is a slow cannon. Want more game puzzles? Try LeetCode 486: Predict the Winner or LeetCode 464: Can I Win. Ready to zap some balls? Head to Solve LeetCode 488 on LeetCode and shoot it today—your coding skills are Zuma-ready!