这是一个祖玛游戏。
一行球放在桌面上，球被涂上了红（ R ）、黄（ Y ）、蓝（ B ）、绿（ G ）和白（ W ）这么几种颜色，同时你也拥有几个球。
每一次，从你拥有的球当中拿出一个，插入到当前行当中（包括最左边和最右边）。然后，如果有三个或更多的同色球挨在一起，然后就消除这几个球。一直这么做直到没有更多的球可以消除。 找到最少的需要插入的球的数量，使得所有的球都可以被删除。如果不能删除所有的球，那么就返回-1 。 初始的行不会拥有三个及以上的连续的同色球。 行中的球的数量不会超过 20，用名为"borad"的输入字符串表示。 你拥有的球不会超过 5 个，用名为"hand"的输入字符串表示。 输入字符串都非空，而且仅包含字符 'R','Y','B','G','W'。
点这里可以在线做题
样例 1: 输入: "WRRBBW", "RB" 输出: -1 解释: WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW
样例 2: 输入: "WWRRBBWW", "WRBRW" 输出: 2 解释: WWRRBBWW -> WWRR[R]BBWW -> WWBBWW -> WWBB[B]WW -> WWWW -> empty
样例 3: 输入:"G", "GGGGG" 输出: 2 解释: G -> G[G] -> GG[G] -> empty
样例 4: 输入: "RBYYBBRRB", "YRBGB" 输出: 3 解释: RBYYBBRRB -> RBYY[Y]BBRRB -> RBBBRRB -> RRRB -> B -> B[B] -> BB[B] -> empty
[题解]
考点： 搜索 题解：基本思路就是搜索，c 数组统计自己各类球的数量，对 board 进行遍历，然后 j 保存一段的起点，i 向后移动至出现不同的球，然后对这段长度判断，根据 inc 判断需要几个球插入，对应的球数量减少，然后截取起点至 j 的区间和 i 至区间终点的两段拼接，继续搜索即可。 public class Solution { /** * @param board: the given board * @param hand: the balls in your hand * @return: the minimal balls you have to insert to remove all the balls on the table */ private int aux(String s, int[] c){ if("".equals(s)) { return 0; } int res = 2 * s.length() + 1; for(int i = 0; i < s.length();){ int j = i++; //j 保存起点 while(i < s.length() && s.charAt(i) == s.charAt(j)) { i++; } int inc = 3 - i + j; //3-(i-j) 判断消除需要几个球 if(c[s.charAt(j)] >= inc){ //如果数量足够 int used = inc <= 0 ? 0 : inc; //如果 inc<=0，不需要 c[s.charAt(j)] -= used; //用掉 s[j] int temp = aux(s.substring(0, j) + s.substring(i), c); //去除 j 至 i 的一段继续搜索 if(temp >= 0) { res = Math.min(res, used + temp); } c[s.charAt(j)] += used; //搜索完成后补充球的数量 } } return res == 2 * s.length() + 1 ? -1 : res; } public int findMinStep(String board, String hand) { // Write your code here int[] c = new int[128]; for(char x : hand.toCharArray()){ c[x]++; } return aux(board, c); } }
更多题解参见