1.题目基本信息

1.1.题目描述

你正在参与祖玛游戏的一个变种。

在这个祖玛游戏变体中，桌面上有 一排 彩球，每个球的颜色可能是：红色 'R'、黄色 'Y'、蓝色 'B'、绿色 'G' 或白色 'W' 。你的手中也有一些彩球。

你的目标是 清空 桌面上所有的球。每一回合：

• 从你手上的彩球中选出 任意一颗 ，然后将其插入桌面上那一排球中：两球之间或这一排球的任一端。

• 接着，如果有出现 三个或者三个以上 且 颜色相同 的球相连的话，就把它们移除掉。

  • 如果这种移除操作同样导致出现三个或者三个以上且颜色相同的球相连，则可以继续移除这些球，直到不再满足移除条件。

• 如果桌面上所有球都被移除，则认为你赢得本场游戏。

• 重复这个过程，直到你赢了游戏或者手中没有更多的球。

给你一个字符串 board ，表示桌面上最开始的那排球。另给你一个字符串 hand ，表示手里的彩球。请你按上述操作步骤移除掉桌上所有球，计算并返回所需的 最少 球数。如果不能移除桌上所有的球，返回 -1 。

1.2.题目地址

https://leetcode.cn/problems/zuma-game/description/

2.解题方法

2.1.解题思路

广度优先搜索

2.2.解题步骤

第一步，预处理。将hand中的字符进行升序排列；构建去除board某一个状态的连续重复次数大于等于3的字符的函数

第二步，进行广度优先搜索

• 2.1.构建广搜维护变量，队列和已遍历集合

• 2.2.枚举当前每一种插入方式，将h[j]插入b的索引为j的间隔位置

• 2.3.剪枝

  • 2.3.1.hand中当前的字符和前一个相同，跳过

  • 2.3.2.保证b[i-1]和h[j]不等

• 2.4.将下一层的合法状态加入到队列中。分为b中连续两个相等和不等的情况进行讨论

3.解题代码

python代码

from collections import deque

class Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        # 思路：广度优先搜索
        # 第一步，预处理。将hand中的字符进行升序排列；构建去除board某一个状态的连续重复次数大于等于3的字符的函数
        hand = "".join(sorted(hand))
        def clean(s:str) -> str:
            n = 1
            while n:
                s, n = re.subn(r'(.)\1{2,}', "", s)
            return s
        # 第二步，进行广度优先搜索
        # 2.1.构建广搜维护变量，队列和已遍历集合
        que = deque([(board, hand, 0)])
        visited = set([(board, hand)])
        while que:
            b, h, step = que.popleft()
            if b == "":
                return step
            # 2.2.枚举当前每一种插入方式，将h[j]插入b的索引为j的间隔位置
            for i, j in product(range(len(b) + 1), range(len(h))):
                # 2.3.剪枝
                # 2.3.1.hand中当前的字符和前一个相同，跳过
                if j > 0 and h[j] == h[j - 1]:
                    continue
                # 2.3.2.保证b[i-1]和h[j]不等
                if i > 0 and b[i - 1] == h[j]:
                    continue
                # 2.4.将下一层的合法状态加入到队列中。分为b中连续两个相等和不等的情况进行讨论
                ok = False
                if 0 < i < len(b) and b[i] == b[i - 1]:
                    if b[i] != h[j]:
                        ok = True
                else:
                    # 和两侧情况都不同的情况无需讨论，纯熵增
                    if i < len(b) and b[i] == h[j]:
                        ok = True
                if ok:
                    newB = clean(b[:i] + h[j] + b[i:])
                    newH = h[:j] + h[j + 1:]
                    if (newB, newH) not in visited:
                        que.append((newB, newH, step + 1))
                        visited.add((newB, newH))
        return -1

4.执行结果