1. 问题描述：
回忆一下祖玛游戏。现在桌上有一串球，颜色有红色(R)，黄色(Y)，蓝色(B)，绿色(G)，还有白色(W)。 现在你手里也有几个球。
每一次，你可以从手里的球选一个，然后把这个球插入到一串球中的某个位置上（包括最左端，最右端）。接着，如果有出现三个或者三个以上颜色相同的球相连的话，就把它们移除掉。重复这一步骤直到桌上所有的球都被移除。
找到插入并可以移除掉桌上所有球所需的最少的球数。如果不能移除桌上所有的球，输出 -1 。
示例 1：
输入：board = "WRRBBW", hand = "RB"
输出：-1
解释：WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW
示例 2：
输入：board = "WWRRBBWW", hand = "WRBRW"
输出：2
解释：WWRRBBWW -> WWRR[R]BBWW -> WWBBWW -> WWBB[B]WW -> WWWW -> empty
示例 3：
输入：board = "G", hand = "GGGGG"
输出：2
解释：G -> G[G] -> GG[G] -> empty
示例 4：
输入：board = "RBYYBBRRB", hand = "YRBGB"
输出：3
解释：RBYYBBRRB -> RBYY[Y]BBRRB -> RBBBRRB -> RRRB -> B -> B[B] -> BB[B] -> empty
提示：
你可以假设桌上一开始的球中，不会有三个及三个以上颜色相同且连着的球。
1 <= board.length <= 16
1 <= hand.length <= 5
输入的两个字符串均为非空字符串，且只包含字符 'R','Y','B','G','W'。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zuma-game
2. 思路分析：
分析题目可以知道最容易想到的是递归的方法，我们可以使用递归搜索所有可能的消除方案，这样肯定是可以求解出答案的，而且数据规模不是特别大应该可以通过。我们可以尝试将手中的球插入到当前board状态中的任意一个位置，使用一个方法来消除掉当前得到的新的状态的长度大于等于3的连续的字符串，为了减少不必要的搜索，我们可以使用记忆型的递归，其中一个哈希表来记录当前的局面，当前的局面由两个状态决定，第一个是当前插入小球之后消除的状态，另外一个状态是当前手中剩余小球的状态，由这两个状态那么就可以唯一确定当前的局面，第二个哈希表来记录当前手中剩余的球的数目，这样方便根据当前的状态插入小球。
3. 代码如下：
import collections
class Solution:
# 获取手中剩余的球的状态
def get(self):
s = ""
for k, v in self.count.items():
s += k
return s
# 循环删除长度大于等于3的连续子串
def clean_up(self, s: str):
t = s
isChange = 1
i = 0
while isChange > 0:
isChange = 0
i = 0
while i < len(s):
j = i + 1
while j < len(s) and s[j] == s[i]: j += 1
if j - i >= 3:
isChange = 1
s = s[0:i] + s[j:]
break
# i = j
i += 1
return s
res = 6
# board表示当前的状态, hand当前手中的剩下球对应的状态
def dfs(self, board: str, hand: str):
if self.dic[board + " " + hand] >= self.res: return
for k, v in self.count.items():
if v > 0:
self.count[k] -= 1
# 当前的球可以插到开始与结尾处
for i in range(len(board) + 1):
# 插入小球之后进行循环消除长度大于等于3的连续的小球
s = self.clean_up(board[0:i] + k + board[i:])
t = s + " " + self.get()
# 当前状态之前不存在或者到达当前状态的步数更小那么更新
if self.dic[t] == 0 or self.dic[t] > self.dic[board + " " + hand] + 1:
self.dic[t] = self.dic[board + " " + hand] + 1
if not s:
self.res = min(self.res, self.dic[t])
self.dfs(s, self.get())
self.count[k] += 1
# 字典dic来记录到达的状态, count记录当前手中球的数目
dic, count = None, None
def findMinStep(self, board: str, hand: str) -> int:
self.dic, self.count = collections.defaultdict(int), collections.defaultdict(int)
for c in hand:
self.count[c] += 1
self.dic[board] = 0
self.dfs(board, self.get())
# 最多操作5次所以当发现答案是6的时候那么返回-1
if self.res == 6: return -1
return self.res