https://leetcode-cn.com/problems/zuma-game/
題目描述回憶一下祖瑪遊戲。現在桌上有一串球，顏色有紅色(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'。
前置知識公司思路面試題困難難度的題目常見的題型有：
本題就是遊戲類題目。如果你是一個前端， 說不定還會考察你如何實現一個 zuma 遊戲。這種遊戲類的題目，可以簡單可以困難， 比如力扣經典的石子遊戲，寶石遊戲等。這類題目沒有固定的解法。我做這種題目的思路就是先暴力模擬，再嘗試優化算法瓶頸。
注意下數據範圍球的數目 <= 5，因此暴力法就變得可行。基本思路是暴力枚舉手上的球可以消除的地方， 我們可以使用回溯法來完成暴力枚舉的過程，在回溯過程記錄最小值即可。由於回溯樹的深度不會超過 5，因此這種解法應該可以 AC。
上面提到的可以消除的地方，指的是「連續相同顏色 + 手上相同顏色的球大於等於 3」，這也是題目說明的消除條件。
因此我們只需要兩個指針記錄連續相同顏色球的位置，如果可以消除，消除即可。
如圖，我們記錄了連續紅球的位置， 如果手上有紅球， 則可以嘗試將其清除，這一次決策就是回溯樹（決策樹）的一個分支。之後我們會撤回到這個決策分支， 嘗試其他可行的決策分支。
以 board = RRBBRR ， hand 為 RRBB 為例，其決策樹為：
其中虛線表示無需手動幹預，系統自動消除。葉子節點末尾的黃色表示全部消除需要的手球個數。路徑上的文字後面的數字表示此次消除需要的手球個數
❝如果你對回溯不熟悉，可以參考下我之前寫的幾篇題解：比如 46.permutations[1]。
❞可以看出， 如果選擇先消除中間的藍色，則只需要一步即可完成。
關於計算連續球位置的核心代碼(Python3):
i = 0
while i < len(board):
j = i + 1
while j < len(board) and board[i] == board[j]: j += 1
# 其他邏輯
# 更新左指針
i = j具體算法：
用哈希表存儲手上的球的種類和個數，這麼做是為了後面「快速判斷連續的球是否可以被消除」。由於題目限制手上求不會超過 5，因此哈希表的最大容量就是 5，可以認為這是一個常數的空間。
回溯。
2.1 確認可以消除的位置，算法參考上面的代碼。
2.2 判斷手上是否有足夠相同顏色的球可以消除。
2.3 回溯的過程記錄全局最小值。
代碼代碼支持：Python3
Python3 Code:
class Solution:
def findMinStep(self, board: str, hand: str) -> int:
def backtrack(board):
if not board: return 0
i = 0
ans = 6
while i < len(board):
j = i + 1
while j < len(board) and board[i] == board[j]: j += 1
balls = 3 - (j - i)
if counter[board[i]] >= balls:
balls = max(0, balls)
counter[board[i]] -= balls
ans = min(ans, balls + backtrack(board[:i] + board[j:]))
counter[board[i]] += balls
i = j
return ans
counter = collections.Counter(hand)
ans = backtrack(board)
return -1 if ans > 5 else ans「複雜度分析」
時間複雜度：