Hard
题目描述
你正在玩一个祖玛游戏的变种。
在这个祖玛游戏变种中，桌面上有一排彩色的球，每个球的颜色可能是红色 ‘R’，黄色 ‘Y’，蓝色 ‘B’，绿色 ‘G’ 或白色 ‘W’。你手中也有一些彩色的球。
你的目标是清空桌面上所有的球。每一回合：
- 从你手里挑选任意一个球，然后把这个球插入到一排球中的某个位置（包括最左端，最右端）。
- 接着，如果有出现三个或者三个以上颜色相同的球相连的话，就把它们移除掉。
- 如果这种移除操作同样导致出现三个或者三个以上且颜色相同的球相连，则继续移除这些球，直到不再有新的三个或者三个以上颜色相同的球相连出现。
- 如果桌面上所有球都被移除，则认为你赢得本场游戏。
- 重复这个过程，直到你赢了游戏或者手中没有更多的球。
给你一个字符串 board，表示桌面上一排球的颜色，一个字符串 hand，表示你手中球的颜色，请你找出清空桌面所需的最少球数。如果不能清空桌面，请返回 -1。
示例 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 个球就可以清空桌面。
提示：
1 <= board.length <= 161 <= hand.length <= 5board和hand只包含字符 ‘R’、‘Y’、‘B’、‘G’ 和 ‘W’- 桌面上一开始的球中，不会有三个及三个以上颜色相同且连续的球
解题思路
这是一道典型的搜索问题，需要用到广度优先搜索（BFS）和记忆化搜索。
核心思路是通过状态空间搜索，每次从手中取一个球插入到桌面的每个可能位置，然后模拟消除过程，直到找到清空桌面的最短路径。
具体步骤：
- 状态表示：使用 (board, hand) 作为状态，其中 board 表示当前桌面状态，hand 表示手中剩余的球
- 状态转移：对于当前状态，尝试从手中取每种颜色的球，插入到桌面的每个位置
- 消除模拟：插入球后，模拟连续消除过程，直到没有三个或以上连续相同颜色的球
- 剪枝优化：
- 使用记忆化避免重复计算相同状态
- 将手中的球按字典序排序，避免状态重复
- 只在有意义的位置插入球（比如插入后能立即形成消除，或者填补空隙）
关键的优化是插入位置的选择：我们只需要在以下位置插入球：
- 桌面两端
- 两个不同颜色球的边界
- 能够立即形成消除的位置
算法使用 BFS 保证找到最优解，时间复杂度虽然较高，但由于数据规模较小（board长度≤16，hand长度≤5），完全可以接受。
代码实现
class Solution {
public:
int findMinStep(string board, string hand) {
sort(hand.begin(), hand.end());
unordered_set<string> visited;
queue<pair<string, string>> q;
q.push({board, hand});
visited.insert(board + " " + hand);
int step = 0;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
auto [curBoard, curHand] = q.front();
q.pop();
if (curBoard.empty()) return step;
for (int j = 0; j < curHand.size(); j++) {
if (j > 0 && curHand[j] == curHand[j-1]) continue;
char ball = curHand[j];
string newHand = curHand.substr(0, j) + curHand.substr(j + 1);
for (int k = 0; k <= curBoard.size(); k++) {
if (k > 0 && k < curBoard.size() && curBoard[k-1] == curBoard[k]) continue;
string newBoard = curBoard.substr(0, k) + ball + curBoard.substr(k);
newBoard = eliminate(newBoard);
string state = newBoard + " " + newHand;
if (visited.find(state) == visited.end()) {
visited.insert(state);
q.push({newBoard, newHand});
}
}
}
}
step++;
}
return -1;
}
private:
string eliminate(string board) {
bool changed = true;
while (changed) {
changed = false;
int i = 0;
while (i < board.size()) {
int j = i;
while (j < board.size() && board[j] == board[i]) j++;
if (j - i >= 3) {
board = board.substr(0, i) + board.substr(j);
changed = true;
} else {
i = j;
}
}
}
return board;
}
};
class Solution:
def findMinStep(self, board: str, hand: str) -> int:
def eliminate(s):
while True:
changed = False
i = 0
while i < len(s):
j = i
while j < len(s) and s[j] == s[i]:
j += 1
if j - i >= 3:
s = s[:i] + s[j:]
changed = True
else:
i = j
if not changed:
break
return s
hand = ''.join(sorted(hand))
visited = set()
queue = deque([(board, hand)])
visited.add(board + " " + hand)
step = 0
while queue:
for _ in range(len(queue)):
cur_board, cur_hand = queue.popleft()
if not cur_board:
return step
for i in range(len(cur_hand)):
if i > 0 and cur_hand[i] == cur_hand[i-1]:
continue
ball = cur_hand[i]
new_hand = cur_hand[:i] + cur_hand[i+1:]
for j in range(len(cur_board) + 1):
if j > 0 and j < len(cur_board) and cur_board[j-1] == cur_board[j]:
continue
new_board = cur_board[:j] + ball + cur_board[j:]
new_board = eliminate(new_board)
state = new_board + " " + new_hand
if state not in visited:
visited.add(state)
queue.append((new_board, new_hand))
step += 1
return -1
public class Solution {
public int FindMinStep(string board, string hand) {
var handChars = hand.ToCharArray();
Array.Sort(handChars);
hand = new string(handChars);
var visited = new HashSet<string>();
var queue = new Queue<(string board, string hand)>();
queue.Enqueue((board, hand));
visited.Add(board + " " + hand);
int step = 0;
while (queue.Count > 0) {
int size = queue.Count;
for (int i = 0; i < size; i++) {
var (curBoard, curHand) = queue.Dequeue();
if (string.IsNullOrEmpty(curBoard)) return step;
for (int j = 0; j < curHand.Length; j++) {
if (j > 0 && curHand[j] == curHand[j-1]) continue;
char ball = curHand[j];
string newHand = curHand.Remove(j, 1);
for (int k = 0; k <= curBoard.Length; k++) {
if (k > 0 && k < curBoard.Length && curBoard[k-1] == curBoard[k]) continue;
string newBoard = curBoard.Insert(k, ball.ToString());
newBoard = Eliminate(newBoard);
string state = newBoard + " " + newHand;
if (!visited.Contains(state)) {
visited.Add(state);
queue.Enqueue((newBoard, newHand));
}
}
}
}
step++;
}
return -1;
}
private string Eliminate(string board) {
bool changed = true;
while (changed) {
changed = false;
int i = 0;
while (i < board.Length) {
int j = i;
while (j < board.Length && board[j] == board[i]) j++;
if (j - i >= 3) {
board = board.Remove(i, j - i);
changed = true;
} else {
i = j;
}
}
}
return board;
}
}
var findMinStep = function(board, hand) {
function removeBalls(s) {
let i = 0;
while (i < s.length) {
let j = i;
while (j < s.length && s[j] === s[i]) {
j++;
}
if (j - i >= 3) {
return removeBalls(s.slice(0, i) + s.slice(j));
}
i = j;
}
return s;
}
function countHand(hand) {
const count = {};
for (let char of hand) {
count[char] = (count[char] || 0) + 1;
}
return count;
}
function dfs(board, handCount) {
board = removeBalls(board);
if (board === '') return 0;
let minSteps = Infinity;
for (let i = 0; i <= board.length; i++) {
for (let color in handCount) {
if (handCount[color] > 0) {
let needBalls = 1;
if (i > 0 && board[i-1] === color) {
if (i < board.length && board[i] === color) {
needBalls = 1;
} else {
let count = 1;
let j = i - 1;
while (j >= 0 && board[j] === color) {
count++;
j--;
}
needBalls = Math.max(0, 3 - count);
}
} else if (i < board.length && board[i] === color) {
let count = 1;
let j = i;
while (j < board.length && board[j] === color) {
count++;
j++;
}
needBalls = Math.max(0, 3 - count);
} else {
needBalls = 3;
}
if (handCount[color] >= needBalls) {
let newBoard = board.slice(0, i) + color.repeat(needBalls) + board.slice(i);
let newHandCount = {...handCount};
newHandCount[color] -= needBalls;
let result = dfs(newBoard, newHandCount);
if (result !== -1) {
minSteps = Math.min(minSteps, result + needBalls);
}
}
}
}
}
return minSteps === Infinity ? -1 : minSteps;
}
const memo = new Map();
function memoizedDfs(board, handCount) {
const key = board + '|' + JSON.stringify(handCount);
if (memo.has(key)) return memo.get(key);
board = removeBalls(board);
if (board === '') return 0;
let minSteps = Infinity;
for (let i = 0; i <= board.length; i++) {
for (let color in handCount) {
if (handCount[color] > 0) {
let needBalls = 3;
if (i > 0 && board[i-1] === color) {
if (i < board.length && board[i] === color) {
needBalls = 1;
} else {
let count = 0;
let j = i - 1;
while (j >= 0 && board[j] === color) {
count++;
j--;
}
needBalls = 3 - count;
}
} else if (i < board.length && board[i] === color) {
let count = 0;
let j = i;
while (j < board.length && board[j] === color) {
count++;
j++;
}
needBalls = 3 - count;
}
if (needBalls > 0 && handCount[color] >= needBalls) {
let newBoard = board.slice(0, i) + color.repeat(needBalls) + board.slice(i);
let newHandCount = {...handCount};
newHandCount[color] -= needBalls;
let result = memoizedDfs(newBoard, newHandCount);
if (result !== -1) {
minSteps = Math.min(minSteps, result + needBalls);
}
}
}
}
}
const result = minSteps === Infinity ? -1 : minSteps;
memo.set(key, result);
return result;
}
return memoizedDfs(board, countHand(hand));
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(N! × M^N) 其中 N 是 board 长度，M 是 hand 长度。最坏情况下需要遍历所有可能的状态组合 |
| 空间复杂度 | O(N! × M^N) 主要用于存储访问过的状态和 BFS 队列 |