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.Constraints:
1 <= board.length <= 161 <= hand.length <= 5boardandhandconsist 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.
Problem Analysis:
At first, we can think of using depth first search to get the answer. We iterate try to insert a ball in some place of the board, and if there is more than 3 consecutive balls that have same color then we remove them from the board. And then check after removed, is there still have more than 3 consecutive same color balls, remove them, … Until no ball in the board, we count the used number of balls in the hand, the mininum number is the answer.
suppose we write a function update to perform the remove ball action. Which position should we insert the ball of hand into the board? First, We can insert the ball of hand with the same color next into the position that has the same color in the board. So it can cause removing operation to take. But it is not enough, here is a counter example.
Suppose the board is “RRWWRRBBRR”, hand is “WB”. If we insert ‘W’ at position 2, so it is “RRWWWRRBBRR”, then perform remove action, it change to “RRRRBBRR”, and then “BBRR”, then we have only ‘B’ in the hand, it can not completely remove. If We insert ‘B’ in position 7, so it is “RRWWRRBBBRR”, then perform remove action, it change to “RRWWRRRR”, and then “RRWW”, now we have only ‘W’ in the hand, it also can not completely remove.
The correctly insertion is first inserting ‘B’ in position 1, so it is “RBRWWRRBBRR”, then inserting ‘W’ in position 3, so it is “RBRWWWRRBBRR”, then perform remove action, “RBRRRBBRR”, “RBBBRR”, “RRR”, “”, so it is completely removed.
Solution
class Solution {
public:
int findMinStep(string board, string hand) {
sort(hand.begin(), hand.end());
queue<string> bq;
queue<string> hq;
queue<int> stepq;
unordered_set<string> visited;
visited.insert(board + '#' + hand);
bq.push(board);
hq.push(hand);
stepq.push(0);
while (!hq.empty()) {
string curBoard = bq.front();
bq.pop();
string curHand = hq.front();
hq.pop();
int curStep = stepq.front();
stepq.pop();
for (int i = 0; i < curBoard.length(); ++i) {
for (int j = 0; j < curHand.length(); ++j) {
if (j > 0 && curHand[j] == curHand[j - 1]) continue;
if (i > 0 && curBoard[i - 1] == curHand[j]) continue;bool worthTrying{false};
if (curBoard[i] == curHand[j]) worthTrying = true;
else if (i > 0 && curBoard[i] == curBoard[i - 1] && curBoard[i] != curHand[j])
worthTrying = true; if (worthTrying) {
string newBoard = updateBoard(curBoard.substr(0, i) + curHand[j] + curBoard.substr(i), i);
if (newBoard.empty()) return curStep + 1;
string newHand = curHand.substr(0, j) + curHand.substr(j + 1);
if (visited.find(newBoard + '#' + newHand) == visited.end()) {
bq.push(newBoard);
hq.push(newHand);
stepq.push(curStep + 1);
visited.insert(newBoard + '#' + newHand);
}
}
}
}
} return -1;
}
string updateBoard(string board, int index) {
if (index < 0) return board; int left{index}, right{index};
while (left > 0 && board[left] == board[left - 1]) --left;
while (right < board.length() && board[right] == board[right + 1]) ++right;
int sameClrLen = right - left + 1;
if (sameClrLen >= 3)
return updateBoard(board.substr(0, left) + board.substr(right + 1), left - 1);
else return board;
}
};
time complexity is O(sizeof(board) * sizeof(hand))
Space complexity is O(sizeof(board) * sizeof(hand))