In this guide, you will get 488. Zuma Game LeetCode Solution with the best time and space complexity. The solution to Zuma Game problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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.
Constraints:
1 <= board.length <= 16
1 <= hand.length <= 5
board and hand consist of the characters 'R', 'Y', 'B', 'G', and 'W'.
The initial row of balls on the board will not have any groups of three or more consecutive balls of the same color.
Complexity Analysis
Time Complexity: O(m^2n^2), where m = |\texttt{board}| and n = |\texttt{hand}|
Space Complexity: O(m^2n^2)
488. Zuma Game LeetCode Solution in C++
class Solution {
public:
int findMinStep(string board, string hand) {
const int ans = dfs(board + "#", hand, {});
return ans == INT_MAX ? -1 : ans;
}
private:
int dfs(string&& board, const string& hand,
unordered_map<string, int>&& mem) {
const string hashKey = board + '#' + hand;
if (const auto it = mem.find(hashKey); it != mem.cend())
return it->second;
board = deDup(board);
if (board == "#")
return 0;
unordered_set<char> boardSet = unordered_set(board.begin(), board.end());
string hs; // hand that is in board
for (const char h : hand)
if (boardSet.contains(h))
hs += h;
if (hs.empty()) // infeasible
return INT_MAX;
int ans = INT_MAX;
for (int i = 0; i < board.size(); ++i)
for (int j = 0; j < hs.size(); ++j) {
// Place hs[j] in board[i].
const string& newHand = hs.substr(0, j) + hs.substr(j + 1);
string newBoard = board.substr(0, i) + hs[j] + board.substr(i);
const int res = dfs(std::move(newBoard), newHand, std::move(mem));
if (res < INT_MAX)
ans = min(ans, 1 + res);
}
return mem[hashKey] = ans;
}
string deDup(string board) {
int start = 0; // the start index of a color sequenece
for (int i = 0; i < board.size(); ++i)
if (board[i] != board[start]) {
if (i - start >= 3)
return deDup(board.substr(0, start) + board.substr(i));
start = i; // Meet a new sequence.
}
return board;
}
}; /* code provided by PROGIEZ */
488. Zuma Game LeetCode Solution in Java
class Solution {
public int findMinStep(String board, String hand) {
Map<String, Integer> mem = new HashMap<>();
final int ans = dfs(board + '#', hand, mem);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
private int dfs(String board, final String hand, Map<String, Integer> mem) {
final String hashKey = board + '#' + hand;
if (mem.containsKey(hashKey))
return mem.get(hashKey);
board = deDup(board);
if (board.equals("#"))
return 0;
Set<Character> boardSet = new HashSet<>();
for (final char c : board.toCharArray())
boardSet.add(c);
StringBuilder sb = new StringBuilder();
for (final char h : hand.toCharArray())
if (boardSet.contains(h))
sb.append(h);
final String hs = sb.toString();
if (sb.length() == 0) // infeasible
return Integer.MAX_VALUE;
int ans = Integer.MAX_VALUE;
for (int i = 0; i < board.length(); ++i)
for (int j = 0; j < hs.length(); ++j) {
// Place hs[j] in board[i].
final String newHand = hs.substring(0, j) + hs.substring(j + 1);
String newBoard = board.substring(0, i) + hs.charAt(j) + board.substring(i);
final int res = dfs(newBoard, newHand, mem);
if (res < Integer.MAX_VALUE)
ans = Math.min(ans, 1 + res);
}
mem.put(hashKey, ans);
return ans;
}
private String deDup(String board) {
int start = 0; // the start index of a color sequenece
for (int i = 0; i < board.length(); ++i)
if (board.charAt(i) != board.charAt(start)) {
if (i - start >= 3)
return deDup(board.substring(0, start) + board.substring(i));
start = i; // Meet a new sequence.
}
return board;
}
} // code provided by PROGIEZ
488. Zuma Game LeetCode Solution in Python
class Solution:
def findMinStep(self, board: str, hand: str) -> int:
def deDup(board):
start = 0 # the start index of a color sequenece
for i, c in enumerate(board):
if c != board[start]:
if i - start >= 3:
return deDup(board[:start] + board[i:])
start = i # Meet a new sequence.
return board
@functools.lru_cache(None)
def dfs(board: str, hand: str):
board = deDup(board)
if board == '#':
return 0
boardSet = set(board)
# hand that is in board
hand = ''.join(h for h in hand if h in boardSet)
if not hand: # infeasible
return math.inf
ans = math.inf
for i in range(len(board)):
for j, h in enumerate(hand):
# Place hs[j] in board[i].
newHand = hand[:j] + hand[j + 1:]
newBoard = board[:i] + h + board[i:]
ans = min(ans, 1 + dfs(newBoard, newHand))
return ans
ans = dfs(board + '#', hand)
return -1 if ans == math.inf else ans # code by PROGIEZ
