How hard is LeetCode 488. Zuma Game?

LeetCode 488. Zuma Game is rated Hard on LeetCode.

What topics does LeetCode 488. Zuma Game cover?

LeetCode 488. Zuma Game is tagged Stack, Breadth-First Search, Memoization, String and Dynamic Programming on LeetCode.

Zuma Game — LeetCode 488 Python Solution

HardStackBreadth-First SearchMemoizationStringDynamic Programming

Problem: #488
Pattern: Stack
Reading time: 5 min
Source: leetcode.com

The problem

You are playing a variation of the game Zuma. In this variation of Zuma, there is a single row of colored balls on a board, where each ball can be colored red 'R', yellow 'Y', blue 'B', green 'G', or white 'W'.

Example

Input: board = "WRRBBW", hand = "RB"
Output: -1
Explanation: It is impossible to clear all the balls. The best you can do is:

Python solution

Python

class Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        def remove(s):
            while len(s):
                next = re.sub(r'B{3,}|G{3,}|R{3,}|W{3,}|Y{3,}', '', s)
                if len(next) == len(s):
                    break
                s = next
            return s

        visited = set()
        q = deque([(board, hand)])
        while q:
            state, balls = q.popleft()
            if not state:
                return len(hand) - len(balls)
            for ball in set(balls):
                b = balls.replace(ball, '', 1)
                for i in range(1, len(state) + 1):
                    s = state[:i] + ball + state[i:]
                    s = remove(s)
                    if s not in visited:
                        visited.add(s)
                        q.append((s, b))
        return -1

Complexity

Measure	Complexity
Time	O(n·m) (typical)
Space	O(n·m) or optimized auxiliary

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 488. Zuma Game is filed here because LeetCode tags it Stack, which is the vocabulary this hub collects.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 488. Zuma Game?: LeetCode 488. Zuma Game is rated Hard on LeetCode.
What topics does LeetCode 488. Zuma Game cover?: LeetCode 488. Zuma Game is tagged Stack, Breadth-First Search, Memoization, String and Dynamic Programming on LeetCode.