Zuma Game

Problem Id: 488 Difficulty: Hard


Intuition

Solution


class Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        # Edge cases
        if not board:
            return 0
        if not hand:
            return -1

        ans = -1
        for i in range(len(board)):
            if i + 1 < len(board) and board[i + 1] == board[i]:
                continue
            if board[i] not in hand:
                continue
            s = board[:i + 1] + board[i] + board[i + 1:]
            s = self.remove(s)
            tmp = self.findMinStep(s, hand.replace(board[i], '', 1))
            if tmp == -1:
                continue
            if ans == -1 or tmp + 1 < ans:
                ans = tmp + 1
        return ans

    def remove(self, s):
        if not s:
            return s

        lo = 0
        hi = 1
        tmp = s[0]
        for i in range(1, len(s)):
            if s[i] == tmp:
                hi += 1
            elif hi - lo >= 3:
                return self.remove(s[:lo] + s[hi:])
            else:
                lo, hi = i, i + 1
                tmp = s[i]
        if hi - lo >= 3:
            return self.remove(s[:lo] + s[hi:])
        return s