Problem statement

https://leetcode.com/problems/zuma-game/

Solution

The only correct way to solve this problem is to use backtracking with memorization. On each step we need to insert ball in all possible places. There can be some optimizations made, but some of them seems logical, but not correct: like if we do not have some color on board, no need to use it - it is not true. For the case"RRYGGYYRRYYGGYRR", "GGBBB" if we do not use B, we will have group of RRRR removed earlier than we need and another RR will stuck here forever.

Complexity

Complexity is potentially O(n^m), where n is number of balls on table and m is number of balls in hand.

Code

class Solution:
    def findMinStep(self, board, hand):
        def de_dup(board):
            prev_en = 0
            for i, c in enumerate(board):
                if c != board[prev_en]:
                    if i - prev_en >= 3:
                        return de_dup(board[:prev_en] + board[i:])
                    prev_en = i
            return board

        @lru_cache(None)
        def dfs(board, hand):
            board = de_dup(board)
            if board == "#": return 0
            if not hand: return inf 
            ans = inf 
            for i in range(len(board)):
                for h_id, h in enumerate(hand):
                    new_hand = hand[:h_id] + hand[h_id+1:]
                    new_board = board[:i] + h + board[i:]
                    ans = min(ans, 1 + dfs(new_board, new_hand))
            return ans

        ans = dfs(board + "#", hand)
        return ans if ans < inf else -1