标题问题链接： https://leetcode-cn.com/problems/zuma-game
难度：困难
通过率：41.6%
标题问题描述:回忆一下祖玛游戏。如今桌上有一串球，颜色有红色(R)，黄色(Y)，蓝色(B)，绿色(G)，还有白色(W)。 如今你手里也有几个球。
每一次，你能够从手里的球选一个，然后把那个球插入到一串球中的某个位置上（包罗最左端，最右端）。接着，若是有呈现三个或者三个以上颜色不异的球相连的话，就把它们移除掉。反复那一步调曲到桌上所有的球都被移除。
找到插入并能够移除掉桌上所有球所需的起码的球数。若是不克不及移除桌上所有的球，输出 -1 。
## 示例: 示例: 输入: "WRRBBW", "RB" 输出: -1 解释: WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW （翻译者标注：手上球已经用完，桌上还剩两个球无法消弭，返回-1）
**输入:** "WWRRBBWW", "WRBRW" **输出:** 2 **解释:** WWRRBBWW -> WWRR[R]BBWW -> WWBBWW -> WWBB[B]WW -> WWWW -> empty **输入:** "G", "GGGGG" **输出:** 2 **解释:** G -> G[G] -> GG[G] -> empty **输入:** "RBYYBBRRB", "YRBGB" **输出:** 3 **解释:** RBYYBBRRB -> RBYY[Y]BBRRB -> RBBBRRB -> RRRB -> B -> B[B] -> BB[B] -> empty标注:
你能够假设桌上一起头的球中，不会有三个及三个以上颜色不异且连着的球。桌上的球不会超越20个，输入的数据中代表那些球的字符串的名字是 "board" 。你手中的球不会超越5个，输入的数据中代表那些球的字符串的名字是 "hand"。输入的两个字符串均为非空字符串，且只包罗字符 R,Y,B,G,W。思绪:思绪一：纯暴力解法（超慢）
思绪二：贪婪算法+回溯（选择能够消弭处所）
间接看思绪二吧！
代码:思绪一：
from itertools import groupby import functools def helper(tmp): while 1: cmp_s = tmp cur = "" for k, item in groupby(tmp): n = len(list(item)) if n > 2: continue cur += k * n if cmp_s == cur: break tmp = cur return cur @functools.lru_cache(None) def dfs(b, h): # print(b, h) if not b: return 0 if not h: return float("inf") res = float("inf") for i in range(len(b) + 1): for j in range(len(h)): tmp = b[:i] + h[j] + b[i:] tmp = helper(tmp) res = min(res, 1 + dfs(tmp, h[:j] + h[j + 1:])) return res res = dfs(board, hand) return -1 if res == float("inf") else res思绪二：
class Solution: def findMinStep(self, board: str, hand: str) -> int: cnt = collections.Counter(hand) def dfs(board): if not board: return 0 res = float("inf") cur_loc = 0 for k, item in itertools.groupby(board): n = len(list(item)) need = max(3 - n, 0) if cnt[k] >= need: cnt[k] -= need res = min(res, need + dfs(board[:cur_loc] + board[cur_loc + n:])) cnt[k] += need cur_loc += n return res return -1 if (res := dfs(board)) == float("inf") else res
0