示例
示例 1：
输入：board = "WRRBBW", hand = "RB"
输出：-1
解释：无法移除桌面上的所有球。可以得到的最好局面是：
- 插入一个 'R' ，使桌面变为 WRRRBBW 。WRRRBBW -> WBBW
- 插入一个 'B' ，使桌面变为 WBBBW 。WBBBW -> WW
桌面上还剩着球，没有其他球可以插入。
示例 2：
输入：board = "WWRRBBWW", hand = "WRBRW"
输出：2
解释：要想清空桌面上的球，可以按下述步骤：
- 插入一个 'R' ，使桌面变为 WWRRRBBWW 。WWRRRBBWW -> WWBBWW
- 插入一个 'B' ，使桌面变为 WWBBBWW 。WWBBBWW -> WWWW -> empty
只需从手中出 2 个球就可以清空桌面。
示例 3：
输入：board = "G", hand = "GGGGG"
输出：2
解释：要想清空桌面上的球，可以按下述步骤：
- 插入一个 'G' ，使桌面变为 GG 。
- 插入一个 'G' ，使桌面变为 GGG 。GGG -> empty
只需从手中出 2 个球就可以清空桌面。
示例 4：
输入：board = "RBYYBBRRB", hand = "YRBGB"
输出：3
解释：要想清空桌面上的球，可以按下述步骤：
- 插入一个 'Y' ，使桌面变为 RBYYYBBRRB 。RBYYYBBRRB -> RBBBRRB -> RRRB -> B
- 插入一个 'B' ，使桌面变为 BB 。
- 插入一个 'B' ，使桌面变为 BBB 。BBB -> empty
只需从手中出 3 个球就可以清空桌面。
解题
class Solution {
public:
string del(string board){
for(int i=0;i<board.size();){
int j=i;
while(j<board.size()&&board[i]==board[j])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<board.size();){
int j=i;
while(j<board.size()&&board[i]==board[j])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;
}
};
本篇文章来源于微信公众号:程序IT圈
原创文章，作者：栈长，如若转载，请注明出处：https://www.cxyquan.com/17897.html
栈长 