Leetcode 488. Zuma game

Recall the Zuma game. Now there is a string of balls on the table, the colors are red (R), yellow (Y), blue (B), green (G), and white (W). Now you also have a few balls in your hand.

Each time, you can choose one from the ball in your hand, and then insert the ball into a certain position in a string of balls (including the leftmost end and the rightmost end). Then, if there are three or more balls of the same color connected, remove them. Repeat this step until all the balls on the table are removed.

Find the minimum number of balls required to insert and remove all balls on the table. If all the balls on the table cannot be removed, -1 is output.

Example:
Input: “WRRBBW”, “RB”
Output: -1
Explanation: WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW (Translator’s note: The ball has been used up, there are two balls left on the table that cannot be eliminated, return -1)

Input: “WWRRBBWW”, “WRBRW”
Output: 2
Explanation: WWRRBBWW -> WWRR[R]BBWW -> WWBBWW -> WWBB[B]WW -> WWWW -> empty

Input: “G”, “GGGGG”
Output: 2
Explanation: G -> G[G] -> GG[G] -> empty

Input: “RBYYBBRRB”, “YRBGB”
Output: 3
Explanation: RBYYBBRRB -> RBYY[Y]BBRRB -> RBBBRRB -> RRRB -> B -> B[B] -> BB[B] -> empty

Note:

You can assume that the table starts at the beginning In the balls of, there will not be three or more balls of the same color and connected.
There will be no more than 20 balls on the table. The name of the string representing these balls in the input data is “board”.
You will not have more than 5 balls in your hand, and the name of the string representing these balls in the input data is “hand”.
The two input strings are both non-empty strings and only contain the characters ‘R’,‘Y’,‘B’,‘G’,‘W’.
Algorithm: dfs+hash. We first count the balls in the player’s hands. Then plug it on the table. Just update a new ball every time.

class Solution {

public:

 string del(string board){

 for(int i=0;i<board.size();){

 int j=i;

 while(j;

 if(ji>=3)

 return del(board.substr(0,i )+board.substr(j));

 else i=j;

}

 return board;

}

 int dfs(string board, unordered_map<char,int>&hash){

 board=del(board);

 if(board.size()==0 )return 0;

 int rs=6,need=0;

 for(int i=0;i<board.size();){

 int j=i;

 while(j;

 need=3-(j-i);

 if(hash[board[i]]>=need){

 hash[board[i]]-=need;

 rs=min(rs,need+dfs(board.substr(0,i)+board.substr(j),hash));

 hash[board[i]]+=need;

}

 i=j;

}

 return rs;

}

 int findMinStep(string board, string hand) {

 unordered_map<char,int>hash;

 for(auto x:hand)hash[x]++;

 int res=dfs(board,hash);

 return res==6?-1:res;

}

};

class Solution {

public:

 string del(string board){

 for(int i=0;i<board.size();){

 int j=i;

 while(j;

 if(ji>=3)

 return del(board.substr(0,i )+board.substr(j));

 else i=j;

}

 return board;

}

 int dfs(string board, unordered_map<char,int>&hash){

 board=del(board);

 if(board.size()==0 )return 0;

 int rs=6,need=0;

 for(int i=0;i<board.size();){

 int j=i;

 while(j;

 need=3-(j-i);

 if(hash[board[i]]>=need){

 hash[board[i]]-=need;

 rs=min(rs,need+dfs(board.substr(0,i)+board.substr(j),hash));

 hash[board[i]]+=need;

}

 i=j;

}

 return rs;

}

 int findMinStep(string board, string hand) {

 unordered_map<char,int>hash;

 for(auto x:hand)hash[x]++;

 int res=dfs(board,hash);

 return res==6?-1:res;

}

};