祖玛游戏

难度: Hard

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

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

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

从你手上的彩球中选出 任意一颗 ，然后将其插入桌面上那一排球中：两球之间或这一排球的任一端。
接着，如果有出现 三个或者三个以上 且 颜色相同 的球相连的话，就把它们移除掉。
- 如果这种移除操作同样导致出现三个或者三个以上且颜色相同的球相连，则可以继续移除这些球，直到不再满足移除条件。
如果桌面上所有球都被移除，则认为你赢得本场游戏。
重复这个过程，直到你赢了游戏或者手中没有更多的球。

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

示例 1：

输入：board = "WRRBBW", hand = "RB"
输出：-1
解释：无法移除桌面上的所有球。可以得到的最好局面是：
- 插入一个 'R' ，使桌面变为 WRRRBBW 。WRRRBBW -> WBBW
- 插入一个 'B' ，使桌面变为 WBBBW 。WBBBW -> WW
桌面上还剩着球，没有其他球可以插入。

示例 2：

输入：board = "WWRRBBWW", hand = "WRBRW"
输出：2
解释：要想清空桌面上的球，可以按下述步骤：
- 插入一个 'R' ，使桌面变为 WWRRRBBWW 。WWRRRBBWW -> WWBBWW
- 插入一个 'B' ，使桌面变为 WWBBBWW 。WWBBBWW -> WWWW -> empty
只需从手中出 2 个球就可以清空桌面。

示例 3：

输入：board = "G", hand = "GGGGG"
输出：2
解释：要想清空桌面上的球，可以按下述步骤：
- 插入一个 'G' ，使桌面变为 GG 。
- 插入一个 'G' ，使桌面变为 GGG 。GGG -> empty
只需从手中出 2 个球就可以清空桌面。

示例 4：

输入：board = "RBYYBBRRB", hand = "YRBGB"
输出：3
解释：要想清空桌面上的球，可以按下述步骤：
- 插入一个 'Y' ，使桌面变为 RBYYYBBRRB 。RBYYYBBRRB -> RBBBRRB -> RRRB -> B
- 插入一个 'B' ，使桌面变为 BB 。
- 插入一个 'B' ，使桌面变为 BBB 。BBB -> empty
只需从手中出 3 个球就可以清空桌面。

提示：

1 <= board.length <= 16
1 <= hand.length <= 5
board 和 hand 由字符 'R'、'Y'、'B'、'G' 和 'W' 组成
桌面上一开始的球中，不会有三个及三个以上颜色相同且连着的球

Submission

运行时间: 632 ms

内存: 26.1 MB

class Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        cache = {}
        hand = ''.join(sorted(list(hand)))

        def dfs(lst, hand):
            if not lst:
                return 0
            if not hand:
                return float('inf')
            if (lst, hand) in cache:
                return cache[(lst, hand)]
            
            res = float('inf')
            for j in range(len(hand)):
                if j > 0 and hand[j] == hand[j - 1]:
                    continue
                for d in range(len(lst)):
                    if d > 0 and lst[d - 1] == hand[j]:
                        continue
                    if lst[d] == hand[j] or (d > 0 and lst[d - 1] == lst[d] and lst[d - 1] != hand[j]):
                        if d + 1 < len(lst) and lst[d] == lst[d + 1] == hand[j]:
                            a = d
                            b = d
                            while a >= 0 and b < len(lst) and lst[a] == lst[b] and ((a - 1 >= 0 and lst[a - 1] == lst[a]) or (b + 1 < len(lst) and lst[b + 1] == lst[b])):
                                x = a
                                while x >= 0 and lst[x] == lst[a]:
                                    x -= 1
                                y = b
                                while y < len(lst) and lst[y] == lst[b]:
                                    y += 1
                                a = x
                                b = y
                            res = min(res, 1 + dfs(lst[:a + 1] + lst[b:], hand[:j] + hand[j + 1:]))
                        else:
                            res = min(res, 1 + dfs(lst[:d] + hand[j] + lst[d:], hand[:j] + hand[j + 1:]))
            cache[(lst, hand)] = res
            return res

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

Explain

该题解采用深度优先搜索（DFS）的思路。首先将手中的球按字典序排序，然后对棋盘进行 DFS。在 DFS 过程中，尝试把手中的球插入到棋盘的所有可能位置，然后进行消除操作。如果最终棋盘被清空，则返回使用的球数；否则返回无穷大。为了避免重复计算，使用记忆化搜索来缓存中间结果。

时间复杂度: O(M * N * (N + M^N))

空间复杂度: O(M * N + M^N * N)

class Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        cache = {}  # 记忆化搜索的缓存
        hand = ''.join(sorted(list(hand)))  # 将手中的球按字典序排序

        def dfs(lst, hand):
            if not lst:  # 棋盘已清空，返回0
                return 0
            if not hand:  # 手中无球，无解，返回无穷大
                return float('inf')
            if (lst, hand) in cache:  # 如果当前状态已计算过，直接返回缓存结果
                return cache[(lst, hand)]
            
            res = float('inf')
            for j in range(len(hand)):  # 枚举手中的球
                if j > 0 and hand[j] == hand[j - 1]:  # 跳过重复的球
                    continue
                for d in range(len(lst)):  # 枚举插入位置
                    if d > 0 and lst[d - 1] == hand[j]:  # 跳过连续相同颜色的位置
                        continue
                    if lst[d] == hand[j] or (d > 0 and lst[d - 1] == lst[d] and lst[d - 1] != hand[j]):
                        if d + 1 < len(lst) and lst[d] == lst[d + 1] == hand[j]:  # 形成三个及以上连续相同颜色的球
                            a = d
                            b = d
                            while a >= 0 and b < len(lst) and lst[a] == lst[b] and ((a - 1 >= 0 and lst[a - 1] == lst[a]) or (b + 1 < len(lst) and lst[b + 1] == lst[b])):  # 向两边扩展，找到最大的消除范围
                                x = a
                                while x >= 0 and lst[x] == lst[a]:  # 向左扩展
                                    x -= 1
                                y = b
                                while y < len(lst) and lst[y] == lst[b]:  # 向右扩展
                                    y += 1
                                a = x
                                b = y
                            res = min(res, 1 + dfs(lst[:a + 1] + lst[b:], hand[:j] + hand[j + 1:]))  # 递归搜索，消除连续的球
                        else:
                            res = min(res, 1 + dfs(lst[:d] + hand[j] + lst[d:], hand[:j] + hand[j + 1:]))  # 递归搜索，插入球
            cache[(lst, hand)] = res  # 缓存当前状态的结果
            return res

        res = dfs(board, hand)
        return res if res != float('inf') else -1  # 如果无解，返回-1；否则返回最少的球数

Explore

将手中的球按字典序排序是为了简化搜索过程并避免重复计算。排序后，相同类型的球会聚集在一起，这使得在深度优先搜索中可以更容易地跳过重复的球，从而避免对相同情况的多次搜索。此外，排序还有助于标准化手中球的状态，使得可以更高效地实现记忆化，因为相同的手中球组合（无论其原始顺序如何）都会被排序成相同的字符串，从而共享相同的缓存结果。

在深度优先搜索中跳过连续相同颜色的球和插入位置是为了减少不必要的计算和避免重复的搜索路径。这种策略减少了搜索空间，因为插入连续相同颜色的球在同一位置通常不会产生不同的结果。此外，跳过这些情况可以避免在相同位置重复尝试相同的球，从而提高算法效率。这种优化保证了算法在探索所有可能的插入和消除组合时更为高效，同时不会错过任何可能的解决方案。

‘向两边扩展，找到最大的消除范围’的策略是为了确保在每次插入球后能最大化消除棋盘上的球。通过检查插入点两侧的球，如果它们颜色相同，就继续向外扩展，直至两侧颜色不再相同。这种方法确保了每次插入后都能触发尽可能大范围的消除，从而减少棋盘上的球数，增加获得最终清空棋盘的可能性。这是一种贪心策略，旨在每次操作中都尽可能达到局部最优解，从而提高整体的解决效率。

在递归搜索时继续尝试其他可能的插入和消除组合即使找到了有效的消除操作，是因为我们的目标是找到消耗最少球数的解决方案。单一的消除操作可能不是最优解，可能存在另一种插入和消除组合，可以使用更少的球达到清空棋盘的目标。因此，算法需要探索所有可能的操作组合，以确保找到确实消耗球数最少的最优解。这种全面探索保证了不仅仅是解决问题，而是以最佳方式解决问题。