在這個祖瑪游戲變體中，桌面上有?一排?彩球，每個球的顏色可能是：紅色?'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 個球就可以清空桌面。

?

public class Solution {public int findMinStep(String board, String hand) {List<Character> boards = new ArrayList<>();for (char c: board.toCharArray()) {boards.add(c);}Map<Character, Integer> hands = new HashMap<>();hands.put('R', 0);hands.put('Y', 0);hands.put('B', 0);hands.put('G', 0);hands.put('W', 0);for (char h: hand.toCharArray()) {hands.put(h, hands.get(h) + 1);}return find(boards, hands);}public int find(List<Character> boards, Map<Character, Integer> hands) {clearBoard(boards);if (boards.size() <= 0) {return 0;}if (empty(hands)) {return -1;}int count = 0;int min = Integer.MAX_VALUE;for (int i = 0; i < boards.size(); i++) {Character c = boards.get(i);count++;if (i >= boards.size() - 1 || boards.get(i + 1) != c) {int need = 3 - count;if (hands.get(c) >= need) {List<Character> small = new ArrayList<>(boards);for (int j = 0; j < count; j++) {small.remove(i - j);}hands.put(c, hands.get(c) - need);int smallerFind = find(small, hands);if (smallerFind > -1) {min = Math.min(min, smallerFind + need);}hands.put(c, hands.get(c) + need);}count = 0;}}return (min == Integer.MAX_VALUE) ? -1 : min;}private void clearBoard(List<Character> board) {int count = 0;boolean cleaned = false;for (int i = 0; i < board.size(); i++) {char c = board.get(i);count++;if (i == board.size() - 1 || board.get(i + 1) != c) {if (count >= 3) {for (int j = 0; j < count; j++) {board.remove(i - j);}cleaned = true;break;}count = 0;}}if (cleaned) {clearBoard(board);}}private boolean empty(Map<Character, Integer> hand) {for (int val: hand.values()) {if (val > 0)return false;}return true;} }

總結

以上是生活随笔為你收集整理的leetcode刷题----祖玛游戏（14）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。