LintCode领扣 题解丨百度面试题：祖玛游戏

这是一个祖玛游戏。

一行球放在桌面上，球被涂上了红（R）、黄（Y）、蓝（B）、绿（G）和白（W）这么几种颜色，同时你也拥有几个球。

每一次，从你拥有的球当中拿出一个，插入到当前行当中（包括最左边和最右边）。然后，如果有三个或更多的同色球挨在一起，然后就消除这几个球。一直这么做直到没有更多的球可以消除。

找到最少的需要插入的球的数量，使得所有的球都可以被删除。如果不能删除所有的球，那么就返回-1。

初始的行不会拥有三个及以上的连续的同色球。

行中的球的数量不会超过20，用名为"borad"的输入字符串表示。

你拥有的球不会超过5个，用名为"hand"的输入字符串表示。

输入字符串都非空，而且仅包含字符 'R','Y','B','G','W'。

在线评测地址：

LintCode 领扣：

​

https://www.lintcode.com/problem/zuma-game/?utm_source=sc-tianchi-sz0817

样例 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"

解释: 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);
}           

}

更多题解参见九章算法官网：

https://www.jiuzhang.com/solution/zuma-game/?utm_source=sc-tianchi-sz0817