?LeetCode刷題實戰(zhàn)488：祖瑪游戲

示例 1：

輸入：board = "WRRBBW", hand = "RB"
輸出：-1
解釋：無法移除桌面上的所有球?？梢缘玫降淖詈镁置媸牵?br mpa-from-tpl="t">- 插入一個 'R'?，使桌面變?yōu)?WRRRBBW 。WRRRBBW -> WBBW
- 插入一個 'B'?，使桌面變?yōu)?WBBBW 。WBBBW -> WW
桌面上還剩著球，沒有其他球可以插入。

示例 2：

輸入：board = "WWRRBBWW", hand = "WRBRW"
輸出：2
解釋：要想清空桌面上的球，可以按下述步驟：
- 插入一個 'R'?，使桌面變?yōu)?WWRRRBBWW 。WWRRRBBWW -> WWBBWW
- 插入一個 'B'?，使桌面變?yōu)?WWBBBWW 。WWBBBWW -> WWWW -> empty
只需從手中出 2?個球就可以清空桌面。

示例 3：

輸入：board = "G", hand = "GGGGG"
輸出：2
解釋：要想清空桌面上的球，可以按下述步驟：
- 插入一個 'G'?，使桌面變?yōu)?GG 。
- 插入一個 'G'?，使桌面變?yōu)?GGG 。GGG -> empty
只需從手中出 2?個球就可以清空桌面。

示例 4：

輸入：board = "RBYYBBRRB", hand = "YRBGB"
輸出：3
解釋：要想清空桌面上的球，可以按下述步驟：
- 插入一個 'Y'?，使桌面變?yōu)?RBYYYBBRRB 。RBYYYBBRRB -> RBBBRRB -> RRRB -> B
- 插入一個 'B'?，使桌面變?yōu)?BB 。
- 插入一個 'B'?，使桌面變?yōu)?BBB 。BBB -> empty
只需從手中出 3?個球就可以清空桌面。

class?Solution?{
public:
????string?del(string?board){
????????for(int?i=0;i????????????int?j=i;
????????????while(j????????????if(j-i>=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????????????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;
????}
};