Last updated on July 20th, 2024 at 04:09 am
Here, We see Zuma Game LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Topics
Depth-First Search
Companies
Baidu
Level of Question
Hard
Zuma Game LeetCode Solution
Table of Contents
Problem Statement
You are playing a variation of the game Zuma.
In this variation of Zuma, there is a single row of colored balls on a board, where each ball can be colored red 'R', yellow 'Y', blue 'B', green 'G', or white 'W'. You also have several colored balls in your hand.
Your goal is to clear all of the balls from the board. On each turn:
- Pick any ball from your hand and insert it in between two balls in the row or on either end of the row.
- If there is a group of three or more consecutive balls of the same color, remove the group of balls from the board.
- If this removal causes more groups of three or more of the same color to form, then continue removing each group until there are none left.
- If there are no more balls on the board, then you win the game.
- Repeat this process until you either win or do not have any more balls in your hand.
Given a string board, representing the row of balls on the board, and a string hand, representing the balls in your hand, return the minimum number of balls you have to insert to clear all the balls from the board. If you cannot clear all the balls from the board using the balls in your hand, return -1.
Example 1:
Input: board = “WRRBBW”, hand = “RB”
Output: -1
Explanation: It is impossible to clear all the balls. The best you can do is:
– Insert ‘R’ so the board becomes WRRRBBW. WRRRBBW -> WBBW.
– Insert ‘B’ so the board becomes WBBBW. WBBBW -> WW.
There are still balls remaining on the board, and you are out of balls to insert.
Example 2:
Input: board = “WWRRBBWW”, hand = “WRBRW”
Output: 2
Explanation: To make the board empty:
– Insert ‘R’ so the board becomes WWRRRBBWW. WWRRRBBWW -> WWBBWW.
– Insert ‘B’ so the board becomes WWBBBWW. WWBBBWW -> WWWW -> empty.
2 balls from your hand were needed to clear the board.
Example 3:
Input: board = “G”, hand = “GGGGG”
Output: 2
Explanation: To make the board empty:
– Insert ‘G’ so the board becomes GG.
– Insert ‘G’ so the board becomes GGG. GGG -> empty.
2 balls from your hand were needed to clear the board.
1. Zuma Game LeetCode Solution C++
class Solution {
public:
int findMinStep(string board, string hand) {
vector<int> freq(26, 0);
for(char c: hand)
freq[c - 'A']++;
unordered_map<string, int> cache;
return dfs(board, freq, cache);
}
int dfs(string board, vector<int>& freq, unordered_map<string, int>& cache) {
string key = board + "#" + serialize(freq);
if(cache.count(key)) {
return cache[key];
}
int r = INT_MAX;
if(board.length() == 0) {
r = 0;
} else {
for(int i = 0; i < board.length(); i++) {
for(int j = 0; j < freq.size(); j++) {
bool worthTrying = false;
if(board[i] - 'A' == j)
worthTrying = true;
else if(0 < i && board[i] == board[i - 1] && board[i] - 'A' != j)
worthTrying = true;
if(freq[j] > 0 && worthTrying) {
board.insert(board.begin() + i, j + 'A');
freq[j]--;
string newStr = updateBoard(board);
int steps = dfs(newStr, freq, cache);
if(steps != -1) {
r = min(r, steps + 1);
}
freq[j]++;
board.erase(board.begin() + i);
}
}
}
}
if(r == INT_MAX) r = -1;
cache[key] = r;
return r;
}
string updateBoard(string board) {
int start = 0;
int end = 0;
int boardLen = board.length();
while(start < boardLen) {
while(end < boardLen && board[start] == board[end]) {
end++;
}
if(end - start >= 3) {
string newBoard = board.substr(0, start) + board.substr(end);
return updateBoard(newBoard);
} else {
start = end;
}
}
return board;
}
string serialize(vector<int>& freq) {
string key = "";
for(int i = 0; i < freq.size(); i++) {
if(freq[i] > 0)
key += to_string((char) i + 'A') + to_string(freq[i]);
}
return key;
}
};
2. Zuma Game LeetCode Solution Java
class Solution {
public int findMinStep(String board, String hand) {
HashMap<Character, Integer> freq = new HashMap<Character, Integer>();
for(int i=0; i<hand.length(); i++){
char c = hand.charAt(i);
freq.put(c, freq.getOrDefault(c, 0) +1);
}
return dfs(board, freq, new HashMap<>());
}
public int dfs(String board, HashMap<Character, Integer> freq, Map<String, Integer> cache) {
if (cache.containsKey(board)) {
return cache.get(board);
}
int r = Integer.MAX_VALUE;
if (board.length() == 0) {
r = 0;
} else {
StringBuilder sb = new StringBuilder(board);
for (int i = 0; i<sb.length(); i++) {
for (char c: freq.keySet()) {
if (freq.get(c) > 0) {
sb.insert(i, c);
freq.put(c, freq.get(c) - 1);
String newBoard = updateBoard(sb.toString());
int temp = dfs(newBoard, freq, cache);
if (temp != -1) {
r = Math.min(r, temp + 1);
}
sb.deleteCharAt(i);
freq.put(c, freq.get(c) + 1);
}
}
}
}
r = r == Integer.MAX_VALUE ? -1 : r;
cache.put(board, r);
return r;
}
public String updateBoard(String board){
int i = 0;
int j = 0;
while (i<board.length()) {
while (j<board.length() && board.charAt(j) == board.charAt(i)) {
j++;
}
if (j-i>=3) {
return updateBoard(board.substring(0, i) + board.substring(j));
} else {
i++;
}
}
return board;
}
}
3. Zuma Game LeetCode Solution JavaScript
var balls = ['R', 'Y', 'B', 'G', 'W'];
var reg = new RegExp(balls.map(ball => '(' + ball + '{2}' + ball + '+)').join('|'));
var handle = function (board) {
if (!board) return board;
var tmp = '';
while (tmp = board.replace(reg, ''), tmp !== board) board = tmp;
return board;
}
var cache = {};
var findMinStep = function (board, hand) {
var key = board + ',' + hand;
if (cache[key]) return cache[key];
var ans = hand.length + 1;
board = handle(board);
if (!board) {
cache[key] = 0;
return 0;
}
if (!hand) {
cache[key] = -1;
return cache[key];
}
var handled = {};
for (var i = 0; i < hand.length; i++) {
var ball = hand[i];
if (handled[ball]) continue;
if (i === hand.length - 1 && board.indexOf(ball.repeat(2)) === -1) continue;
handled[ball] = true;
for (var idx = 0; idx <= board.length; idx++) {
if (board[idx] === ball || idx && board[idx] === board[idx - 1] && board[idx] !== ball) {
var count = findMinStep(board.slice(0, idx) + ball + board.slice(idx), hand.slice(0, i) + hand.slice(i + 1));
if (count === -1) continue;
count++;
ans = Math.min(ans, count);
}
}
}
cache[key] = ans > hand.length ? -1 : ans;
return cache[key];
};
4. Zuma Game LeetCode Solution Python
class Solution(object):
def findMinStep(self, board, hand):
def remove_same(s, i):
if i < 0:
return s
left = right = i
while left > 0 and s[left-1] == s[i]:
left -= 1
while right+1 < len(s) and s[right+1] == s[i]:
right += 1
length = right - left + 1
if length >= 3:
new_s = s[:left] + s[right+1:]
return remove_same(new_s, left-1)
else:
return s
hand = "".join(sorted(hand))
q = collections.deque([(board, hand, 0)])
visited = set([(board, hand)])
while q:
curr_board, curr_hand, step = q.popleft()
for i in range(len(curr_board)+1):
for j in range(len(curr_hand)):
if j > 0 and curr_hand[j] == curr_hand[j-1]:
continue
if i > 0 and curr_board[i-1] == curr_hand[j]:
continue
pick = False
if i < len(curr_board) and curr_board[i] == curr_hand[j]:
pick = True
if 0<i<len(curr_board) and curr_board[i-1] == curr_board[i] and curr_board[i] != curr_hand[j]:
pick = True
if pick:
new_board = remove_same(curr_board[:i] + curr_hand[j] + curr_board[i:], i)
new_hand = curr_hand[:j] + curr_hand[j+1:]
if not new_board:
return step + 1
if (new_board, new_hand) not in visited:
q.append((new_board, new_hand, step+1))
visited.add((new_board, new_hand))
return -1