《Zuma Game》（祖玛游戏）是 LeetCode 上的第 488 题，这是一个中等难度的题目，主要考察的是深度优先搜索（DFS）和广度优先搜索（BFS）的算法应用。

题目描述

在一个二维的平面中，有一些彩球按顺序排列成一行，你需要通过射出彩球来消除这些彩球。当三个或更多相同颜色的彩球相连时，这些彩球会被消除。你需要找到消除所有彩球所需的最少射击次数。

输入：

• board：一个字符串，表示初始彩球的排列。
• hand：一个字符串，表示你手中持有的彩球。

输出：

• 返回消除所有彩球所需的最少射击次数。如果无法消除所有彩球，则返回 -1。

示例

输入：board = "WRRBBW", hand = "RB" 输出：-1 解释：无法通过手中的彩球消除所有彩球。

1. 射击手中的 'R' 到位置 3，使得 "WWRRBBWW" 变为 "WWRRRBBWW"。
2. 射击手中的 'B' 到位置 6，使得 "WWRRRBBWW" 变为 "WWRRRBBBW"。 这时，三个 'R' 和三个 'B' 相连，被消除，剩下的 "WWW" 也会被自动消除。

   解题思路

深度优先搜索（DFS）：

• 从左到右遍历 board，找到第一个可以插入的位置。
• 尝试将手中的彩球插入到该位置，并递归地进行下一步搜索。
• 每次插入后，检查是否有连续的三个或更多相同颜色的彩球，如果有则消除它们，并继续递归搜索。
• 记录每次搜索的结果，找到最少射击次数。

代码实现（DFS 示例）

class Solution: def findMinStep(self, board: str, hand: str) -> int: from collections import Counter

    def clean_board(b):
        # 消除连续的三个或更多相同颜色的彩球
        j = 0
        while j < len(b):
            k = j
            while k < len(b) and b[k] == b[j]:
                k += 1
            if k - j >= 3:
                b = b[:j] + b[k:]
                j = 0
            else:
                j = k
        return b

    def dfs(b, h):
        if not b:
            return 0
        b = clean_board(b)
        cnt = Counter(h)
        res = float('inf')
        j = 0
        while j < len(b):
            k = j
            while k < len(b) and b[k] == b[j]:
                k += 1
            need = 3 - (k - j)
            if cnt[b[j]] >= need:
                cnt[b[j]] -= need
                res = min(res, dfs(b[:j] + b[k:], ''.join(cnt.elements())) + need)
                cnt[b[j]] += need
            j = k
        return res

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

sol = Solution() print(sol.findMinStep("WWRRBBWW", "WRBRW")) # 输出：2 print(sol.findMinStep("WRRBBW", "RB")) # 输出：-1

关键点

1. 递归与回溯：通过递归尝试每一种可能的插入方式，并在回溯时恢复状态。
2. 状态清理：在每次插入后，需要清理 board 中的连续相同颜色的彩球。
3. 剪枝优化：如果当前状态无法继续消除彩球，则提前返回，避免无效搜索。

通过以上思路和代码实现，可以有效地解决 LeetCode 488 题《Zuma Game》。希望这个详细的解答对你有所帮助！如果有更多问题，欢迎继续提问。