题目描述
回忆一下祖玛游戏。现在桌上有一串球，颜色有红色(R)，黄色(Y)，蓝色(B)，绿色(G)，还有白色(W)。
现在你手里也有几个球。
每一次，你可以从手里的球选一个，然后把这个球插入到一串球中的某个位置上（包括最左端，最右端）。
接着，如果有出现三个或者三个以上颜色相同的球相连的话，就把它们移除掉。
重复这一步骤直到桌上所有的球都被移除。
找到插入并可以移除掉桌上所有球所需的最少的球数。如果不能移除桌上所有的球，输出 -1 。
示例:
输入: "WRRBBW", "RB"
输出: -1
解释: WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW
（翻译者标注：手上球已经用完，桌上还剩两个球无法消除，返回-1）
输入: "WWRRBBWW", "WRBRW"
输出: 2
解释: WWRRBBWW -> WWRR[R]BBWW -> WWBBWW -> WWBB[B]WW -> WWWW -> empty
输入:"G", "GGGGG"
输出: 2
解释: G -> G[G] -> GG[G] -> empty
输入: "RBYYBBRRB", "YRBGB"
输出: 3
解释: RBYYBBRRB -> RBYY[Y]BBRRB -> RBBBRRB -> RRRB -> B -> B[B] -> BB[B] -> empty
标注:
你可以假设桌上一开始的球中，不会有三个及三个以上颜色相同且连着的球。
桌上的球不会超过20个，输入的数据中代表这些球的字符串的名字是 "board" 。
你手中的球不会超过5个，输入的数据中代表这些球的字符串的名字是 "hand"。
输入的两个字符串均为非空字符串，且只包含字符 'R','Y','B','G','W'。
算法1
由于是求最小步数，使用了BFS宽度搜索。
好在数据不大 在TLE的边缘过了
20200822补:虽然代码慢，但是我突然发现leetcode加强数据后 我是现在本站唯一能ac lt 488的代码了
C++ 代码
class Solution {
public:
struct ELE {
string board;
string hand;
int step;
};
class CCC {
public:
bool operator() (const ELE &a, const ELE &b) const {
if (a.board < b.board) return true;
else if (a.board == b.board) {
if (a.hand < b.hand) return true;
else if (a.hand == b.hand) {
if (a.step < b.step) return true;
}
}
return false;
}
};
set<struct ELE, CCC> record;
string RemoveBall( string insBoard, int& idx)
{
int count = 0; string ret;
int l = idx; int r = idx;
while (l >= 0 && insBoard[l] == insBoard[idx]) l--;
while (r < insBoard.size() && insBoard[r] == insBoard[idx]) r++;
if (r - l >= 4) {
ret = insBoard.substr(0, l+1) + insBoard.substr(r);
idx = l;
}
else {
ret = insBoard;
}
return ret;
}
int findMinStep(string board, string hand) {
queue<struct ELE> q;
q.push({ board,hand,0 });
record.insert({ board,hand,0 });
while (q.size()) {
struct ELE a = q.front(); q.pop();
int step = a.step;
if (a.board.empty()) return a.step;
else if (a.hand.empty()) continue;
for (int i = 0; i < a.hand.size(); i++) {
string curh = a.hand.substr(0, i) + a.hand.substr(i + 1);
char insertChar = a.hand[i];
for (int j = 0; j < a.board.size(); j++) {
string insBoard = a.board.substr(0, j) + insertChar + a.board.substr(j);
int t = j; string out = insBoard; string input ;
while (out.size() != input.size()) {
input = out;
out = "";
out = RemoveBall(input, t);
}
insBoard = out;
if (record.count({ insBoard ,curh }) == 0) {
record.insert({ insBoard, curh });
q.push({ insBoard, curh,a.step+1 });
}
}
}
}
return -1;
}
};
算法2
同上 BFS
C++ 代码
class Solution {
public:
map<pair<string,string>,int> record;
string RemoveBall( string insBoard, int& idx)
{
int count = 0; string ret;
int l = idx; int r = idx;
while (l >= 0 && insBoard[l] == insBoard[idx]) l--;
while (r < insBoard.size() && insBoard[r] == insBoard[idx]) r++;
if (r - l >= 4) {
ret = insBoard.substr(0, l+1) + insBoard.substr(r);
idx = l;
}
else {
ret = insBoard;
}
return ret;
}
int findMinStep(string board, string hand) {
queue<pair<string, string>> q;
q.push({ board,hand });
record[{ board, hand }] = 0;
while (q.size()) {
pair<string,string> curr = q.front();
int step = record[curr];
q.pop();
if (curr.first.empty()) return record[curr];
else if (curr.second.empty()) continue;
for (int i = 0; i < curr.second.size(); i++) {
string currHand = curr.second.substr(0, i) + curr.second.substr(i + 1);
char insertChar = curr.second[i];
for (int j = 0; j < curr.first.size(); j++) {
string insBoard = curr.first.substr(0,j)+ insertChar+ curr.first.substr(j);
int t = j; string out = insBoard; string input ;
while (out.size() != input.size()) {
input = out;
out = "";
out = RemoveBall(input, t);
}
insBoard = out;
if (record.count({ insBoard ,currHand }) == 0) {
record[{ insBoard, currHand }] = step + 1;
q.push({ insBoard, currHand });
}
}
}
}
return -1;
}
};
dfs暴力遍历 只能过16个样例
优化中
int ans = 99999999;
bool removeBall(string& board, int& idx)
{
if (board.empty()) return false;
int l = idx; int r = idx;
while (l > 0 && board[l] == board[l - 1]) l--;
while (r < board.size() - 1 && board[r] == board[r + 1]) r++;
if (r - l >= 2) {
board = board.substr(0, l) + board.substr(r+1);
idx = l;return true;
}
return false;
}
//while (removeBall(board, idx)) {}
void dfs(string board, string hand,int step)
{
if (board.empty()) { ans = min(ans, step); return; }
else if (hand.empty()) { return; }
if (step >= ans) return;
for (int i = 0; i < hand.size(); i++) {
for (int j = 0; j < board.size(); j++) {
string boardCopy = board;
string handCopy = hand;
char insertBall = handCopy[i];
handCopy = handCopy.substr(0, i) + handCopy.substr(i + 1);
boardCopy = boardCopy.substr(0, j) + insertBall + boardCopy.substr(j );
int idx = j;
while (removeBall(boardCopy, idx)) {}
dfs(boardCopy, handCopy, step + 1);
}
}
return;
}
int findMinStep(string board, string hand) {
dfs(board, hand,0);
if (ans == 99999999) return -1;
return ans;
}
int main()
{
//cout << findMinStep("RRWWRRBBRR","WB");
cout << findMinStep("G", "GGGGG");
return 0;
}
