题目描述

Think about Zuma Game. You have a row of balls on the table, colored red(R), yellow(Y), blue(B), green(G), and white(W). You also have several balls in your hand.

Each time, you may choose a ball in your hand, and insert it into the row (including the leftmost place and rightmost place). Then, if there is a group of 3 or more balls in the same color touching, remove these balls. Keep doing this until no more balls can be removed.

Find the minimal balls you have to insert to remove all the balls on the table. If you cannot remove all the balls, output -1.

Examples:

Input: "WRRBBW", "RB"
Output: -1
Explanation: WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW

Input: "WWRRBBWW", "WRBRW"
Output: 2
Explanation: WWRRBBWW -> WWRR[R]BBWW -> WWBBWW -> WWBB[B]WW -> WWWW -> empty

Input:"G", "GGGGG"
Output: 2
Explanation: G -> G[G] -> GG[G] -> empty 

Input: "RBYYBBRRB", "YRBGB"
Output: 3
Explanation: RBYYBBRRB -> RBYY[Y]BBRRB -> RBBBRRB -> RRRB -> B -> B[B] -> BB[B] -> empty 

Note:

1. You may assume that the initial row of balls on the table won’t have any 3 or more consecutive balls with the same color.
2. The number of balls on the table won’t exceed 20, and the string represents these balls is called “board” in the input.
3. The number of balls in your hand won’t exceed 5, and the string represents these balls is called “hand” in the input.
4. Both input strings will be non-empty and only contain characters ‘R’,’Y’,’B’,’G’,’W’.

题意：回忆一下祖玛游戏。现在桌上有一串球，颜色有红色(R)，黄色(Y)，蓝色(B)，绿色(G)，还有白色(W)。 现在你手里也有几个球。

每一次，你可以从手里的球选一个，然后把这个球插入到一串球中的某个位置上（包括最左端，最右端）。接着，如果有出现三个或者三个以上颜色相同的球相连的话，就把它们移除掉。重复这一步骤直到桌上所有的球都被移除。找到插入并可以移除掉桌上所有球所需的最少的球数。如果不能移除桌上所有的球，输出 -1 。

算法1

(搜索+剪枝) $O(n^2)$

题解：这一题数据量很小，一般就是使用搜索+剪枝来做的题。考虑每一轮桌上球个数为n，手上每种颜色的球个数在hash中。

剪枝策略1:枚举这一轮插球的时候，至少需要使其能够合并一次，放一个或者两个球。

剪枝策略2:枚举每一个球插入位置的时候，只枚举放在和该球颜色一样的球左边。

剪枝策略3:枚举每一个球插入位置的时候，如果相邻两个位置的球颜色一样，只枚举一次

剪枝策略4:统计手上每种颜色的球的个数。在遍历桌子上的球时如果当前颜色连续的球的个数为x，那么如果想当前轮次消除这个球，就至少需要3 - x个球，如果手上的这种颜色球不够多，说明当前这种颜色的球暂时不能消去（可以等待消除别的球后的合并使其合法，如BYYB，我们手上只有一个B，说明这轮不能消除B，但是当把YY消去变成BB的时候，我们就可以消除B啦）

剪枝策略5:如果当前放入球的个数已经大于等于最优解了就没有必要搜索了。

C++ 代码

class Solution {
public:
    int res = INT_MAX;
    unordered_map<char,int> hash;
    int findMinStep(string board, string hand) {
        int n = board.length(),m = hand.length();
        for(auto x: hand) hash[x] ++;
        dfs(board,0);
        return res == INT_MAX ? -1 :res;
    }
    void dfs(string board,int cnt)
    {
        board = parse(board);
        if(board == ""){res = min(res,cnt);return;}
        if(cnt >= res) return;
        int n = board.length(),need = 0;
        for(int i = 0;i < n;)
        {
            int j = i;
            while(j < n && board[i] == board[j]) j++;
            need = 3 - ( j - i);
            if(hash[board[i]] >= need){
                hash[board[i]] -= need;
                dfs(board.substr(0,i) + board.substr(j),cnt + need);
                hash[board[i]] += need;
            }
            i = j;
        }
    }
    string parse(string s)
    {
        int n = s.length();
        for(int i = 0 ; i < n ;)
        {
            int j = i;
            while(j < n && s[j] == s[i])j ++;
            if(j - i >= 3)
                return parse(s.substr(0,i) + s.substr(j));
            i = j;
        }
        return s;
    }
};