力扣解题思路：488. 祖玛游戏

思路：
实际上就是简单的消消乐，如果时间允许，最简单的暴力递归法也是可以的，就是把所有字母插入所有的位置，取最短且可以消去的插入球数即可。但是这样无脑插入是很浪费时间的，所以我们在插入的时候应该先选好合适的位置，分一下两种情况：
（1）插入一个或两个颜色相同的球引发连锁反响。
（2）往两个颜色相同的球中间插入一个颜色不同的球（为什么要这么做呢？见特殊测试用例二）。

注意两个特殊的测试用例：

测试用例一：
"WWRRGGRRWWRRGGRRWW", "GG"
无论怎么插入，都无法完全消除，结果应是-1。

测试用例二：
"RRWWRRBBRR", "WB"
"R(B)RWWRRBBRR" -> "R(B)RWW(W)RRBBRR" -> ""
结果应是2。

首先我们需要一个方法来用于消去字符串，返回消去后的结果：

    private StringBuilder eliminate(StringBuilder sb) {
        boolean flag = true;
        while (flag) {
            flag = false;
            for (int i = 0; i < sb.length(); i++) {
                int j = i + 1;
                while (j < sb.length() && sb.charAt(j) == sb.charAt(i)) {
                    j++;
                }
                if (j - i >= 3) {
                    sb.delete(i, j);
                    flag = true;
                }
            }
        }
        return sb;
    }

我们使用Map来保存可用字符的数量，用数组或者hashMap都可以，这里为了简洁我们使用数组：

    private int result = Integer.MAX_VALUE;
    private int[] map = new int[26];
    private char[] colors = {'R', 'Y', 'B', 'G', 'W'};
    public int findMinStep(String board, String hand) {
        for (int i = 0; i < hand.length(); i++) {
            map[hand.charAt(i) - 'A']++;
        }
        dfs(new StringBuilder(board), 0);
        return result == Integer.MAX_VALUE ? -1 : result;
    }

接下来就是递归方法的编写，我们先定义递归的出口：
1.到达递归终点(目标字符串已被全部消除)
2.目前已用的字符个数比之前result中的更大（因此不必继续递归）

        if (step >= result) return;
        if (board.length() == 0) {
            result = Math.min(step, result);
            return;
        }

接下来就可以分情况讨论：
（1）插入一个或两个颜色相同的球引发连锁反响。
（2）往两个颜色相同的球中间插入一个颜色不同的球。

for (int i = 0; i < board.length(); i++) {
            char c = board.charAt(i);
            int j = i;
            while (j + 1 < board.length() && board.charAt(j + 1) == c) {
                j++;
            }//统计同色球个数
            if (j == i && map[c - 'A'] >= 2) {  //只有单个球
                StringBuilder tmp = new StringBuilder(board);
                tmp.insert(i, c + "" + c);
                map[c - 'A'] -= 2;
                dfs(eliminate(tmp), step + 2);
                map[c - 'A'] += 2;
            } else if (j == i + 1) {    //存在两个颜色相同且相邻的球
                if (map[c - 'A'] >= 1) {
                    StringBuilder tmp = new StringBuilder(board);
                    tmp.insert(i, c);
                    map[c - 'A']--;
                    dfs(eliminate(tmp), step + 1);
                    map[c - 'A']++;
                }
                for (char color : colors) {
                    if (color == c) {
                        continue;
                    }
                    if (map[color - 'A'] >= 1) {
                        StringBuilder tmp = new StringBuilder(board);
                        tmp.insert(i + 1, color);   //尝试往这两个颜色相同且相邻的球中间插入一个颜色不同的球
                        map[color - 'A']--;
                        dfs(eliminate(tmp), step + 1);
                        map[color - 'A']++;
                    }
                }
            }

完整代码如下：

    private int result = Integer.MAX_VALUE;
    private int[] map = new int[26];
    private char[] colors = {'R', 'Y', 'B', 'G', 'W'};
    public int findMinStep(String board, String hand) {
        for (int i = 0; i < hand.length(); i++) {
            map[hand.charAt(i) - 'A']++;
        }
        dfs(new StringBuilder(board), 0);
        return result == Integer.MAX_VALUE ? -1 : result;
    }
    private void dfs(StringBuilder board, int step) {
        if (step >= result) return;
        if (board.length() == 0) {
            result = Math.min(step, result);
            return;
        }
        for (int i = 0; i < board.length(); i++) {
            char c = board.charAt(i);
            int j = i;
            while (j + 1 < board.length() && board.charAt(j + 1) == c) {
                j++;
            }
            if (j == i && map[c - 'A'] >= 2) {  //只有单个球
                StringBuilder tmp = new StringBuilder(board);
                tmp.insert(i, c + "" + c);
                map[c - 'A'] -= 2;
                dfs(eliminate(tmp), step + 2);
                map[c - 'A'] += 2;
            } else if (j == i + 1) {    //存在两个颜色相同且相邻的球
                if (map[c - 'A'] >= 1) {
                    StringBuilder tmp = new StringBuilder(board);
                    tmp.insert(i, c);
                    map[c - 'A']--;
                    dfs(eliminate(tmp), step + 1);
                    map[c - 'A']++;
                }
                for (char color : colors) {
                    if (color == c) {
                        continue;
                    }
                    if (map[color - 'A'] >= 1) {
                        StringBuilder tmp = new StringBuilder(board);
                        tmp.insert(i + 1, color);   //尝试往这两个颜色相同且相邻的球中间插入一个颜色不同的球
                        map[color - 'A']--;
                        dfs(eliminate(tmp), step + 1);
                        map[color - 'A']++;
                    }
                }
            }
        }
    }
    private StringBuilder eliminate(StringBuilder sb) {
        boolean flag = true;
        while (flag) {
            flag = false;
            for (int i = 0; i < sb.length(); i++) {
                int j = i + 1;
                while (j < sb.length() && sb.charAt(j) == sb.charAt(i)) {
                    j++;
                }
                if (j - i >= 3) {
                    sb.delete(i, j);
                    flag = true;
                }
            }
        }
        return sb;
    }