03 Sept 2025•Python•Hard

Zuma Game

find minimum balls needed to clear board using dfs with memoization, trying to form groups of 3+.

View original LeetCode question

use dfs to try all possibilities. for each consecutive group in board, calculate how many balls needed to make group of 3+. if we have enough in hand, use them, remove group, shrink board (remove new groups of 3+), and recurse.

shrink function recursively removes groups of 3+ consecutive same characters. base cases: empty board returns 0, empty hand returns infinity. try all groups, take minimum.

algorithm

  • find consecutive groups in board
  • for each group, calculate need = 3 - group_length
  • if hand has enough, use them and recurse
  • shrink board after removing group
  • return minimum balls needed

complexity

exponential time in worst case, but pruning helps. O(n) space for recursion stack where n is board length.

Solution files

Python•zuma-game/solution.py
from collections import Counter

class Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        def dfs(board, hand):
            if not board:
                return class="syntax-number">0
            if not hand:
                return float(class="syntax-string">'inf')

            res = float(class="syntax-string">'inf')
            i = class="syntax-number">0
            while i < len(board):
                j = i + class="syntax-number">1
                while j < len(board) and board[j] == board[i]:
                    j += class="syntax-number">1
                need = class="syntax-number">3 - (j - i)
                if hand[board[i]] >= need:
                    new_hand = hand.copy()
                    new_hand[board[i]] -= need
                    new_board = board[:i] + board[j:]
                    new_board = Solution.shrink(new_board)
                    res = min(res, need + dfs(new_board, new_hand))
                i = j

            return res

        board_count = Counter(board)
        hand_count = Counter(hand)
        result = dfs(board, hand_count)
        return -class="syntax-number">1 if result == float(class="syntax-string">'inf') else result

    @staticmethod
    def shrink(board):
        i = class="syntax-number">0
        while i < len(board):
            j = i + class="syntax-number">1
            while j < len(board) and board[j] == board[i]:
                j += class="syntax-number">1
            if j - i >= class="syntax-number">3:
                return Solution.shrink(board[:i] + board[j:])
            i = j
        return board