你正在参与祖玛游戏的一个变种。
在这个祖玛游戏变体中，桌面上有 一排 彩球，每个球的颜色可能是：红色 '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 个球就可以清空桌面。
示例 4：
输入：board = "RBYYBBRRB", hand = "YRBGB" 输出：3 解释：要想清空桌面上的球，可以按下述步骤： - 插入一个 'Y' ，使桌面变为 RBYYYBBRRB 。RBYYYBBRRB -> RBBBRRB -> RRRB -> B - 插入一个 'B' ，使桌面变为 BB 。 - 插入一个 'B' ，使桌面变为 BBB 。BBB -> empty 只需从手中出 3 个球就可以清空桌面。
提示：
1 <= board.length <= 161 <= hand.length <= 5board和hand由字符'R'、'Y'、'B'、'G'和'W'组成- 桌面上一开始的球中，不会有三个及三个以上颜色相同且连着的球
Related Topics
深度优先搜索方法，board 结尾借个空格好处理点
上班摸鱼，凑合摸了一个小时多，水平有限
深度优先搜索，
删除连续相同颜色的，我在结尾添加了一个空格，代码稍微好写点具体参见reductionChars方法，不过这个还是写的不太完美，需要递归处理，应该有不用递归的写法的，回头再尝试
具体还是看代码吧，有一些注解，应该能看看吧
class Solution {
HashSet<String> visited = new HashSet<>();
int min = 100;
public int findMinStep(String board, String hand) {
//借个空结尾代码好处理点
board = board+" ";
boolean[] handUsed = new boolean[hand.length()];
char[] boardChars = board.toCharArray();
dfs(boardChars,hand,handUsed);
//如果是100表示不能全消除
return min==100?-1:min;
}
public void dfs(char[] chars, String hand , boolean[] handUsed){
if (chars.length==1){
//统计用了几个
int usedCount = 0;
for (boolean used : handUsed) {
if (used){
usedCount++;
}
}
min = Math.min(min,usedCount);
return ;
}
//剪枝已经处理过的情况
if (visited.contains(new String(chars))){
return ;
}
//记录下当前情况已经处理过
visited.add(new String(chars));
//从handUsed所有在handUsed中没有标记的已用过的位置中取一个字符
for (int idx = 0; idx < handUsed.length; idx++) {
if (handUsed[idx]){
continue;
}
//标记已使用
handUsed[idx] = true;
//构造所有可能的组合情况
List<char[]> list = insertChar(chars,hand.charAt(idx));
for (char[] charArr : list) {
//继续递归
dfs(reductionChars(charArr),hand,handUsed);
}
//回溯标记未使用
handUsed[idx] = false;
}
}
/**
* 往`char[] chars` 数组中所有能插入的位置插入一个新的字符`c`
* 如果原来的被 插入位置和当前插入字符相同，只插入到后面一个位置
* @param chars
* @param c
* @return
*/
public List<char[]> insertChar(char[] chars, char c){
List<char[]> list = new ArrayList<>();
int idx = -1;
while (++idx < chars.length){
while (chars[idx]==c){
idx++;
}
char[] newChars = new char[chars.length+1];
System.arraycopy(chars,0,newChars,0,idx);
System.arraycopy(chars,idx,newChars,idx+1,chars.length-idx);
newChars[idx] = c;
list.add(newChars);
}
return list;
}
/**
* 删除字符串数组中连续出现次数大于等于3的区段内容
* @param chars
* @return
*/
public char[] reductionChars(char[] chars){
//记录下当前的长度
int length = chars.length;
int idx = 0;
char lastChar = chars[0];
int lastCharCount = 1;
while (++idx < chars.length){
if (chars[idx] == lastChar){
lastCharCount++;
}else{
//当前字符和前一个不同
if (lastCharCount>=3){
//从当前位置往前删除掉lastCharCount个
char[] newChars = new char[chars.length-lastCharCount];
System.arraycopy(chars,0,newChars,0,idx-lastCharCount);
System.arraycopy(chars,idx,newChars,idx-lastCharCount,chars.length-idx);
chars = newChars;
idx -= lastCharCount;
}
lastChar = chars[idx];
lastCharCount = 1;
}
}
//如果没有能处理删除掉的字符则直接返回
//如果长度发生了变化，尝试再处理一次，防止 WWRRRWW 变成了 WWWW后还要再处理一次的情况
return length == chars.length?chars:reductionChars(chars);
}
}
发表评论