488. 祖玛游戏

image-20211109101310993

解题思路：

​ 在刚开始看题时虽然想到了可能要用dfs来解决，但是对于每次插入球后的消球过程没有特别好的解决思路，后续参考了其他的题解后才得到了快慢指针用于处理插入球后的消除过程的Update思路，并且也考虑到了记忆化搜索优化超时。

  • 整个解题过程分为两个阶段，DFS+记忆化搜索+回溯与每次插入后的消除过程
    • 每次插入后的消除过程采用了快慢指针的方式，设slow指针和fast指针的初始值为0，fast遍历插入球后的整个字符串。
      • 若fast<board.size()且board[fast]==board[slow]则代表当前slow和fast所指代的球的颜色是相同的，进行continue的操作
      • 若fast-slow>=3则代表当前慢指针slow到快指针fast之间为三个或三个颜色相同以上的球，因此用string.erase来进行消除操作，同时设fast=0，需要重新进行遍历
      • 每次遍历结束的末尾需要将slow=fast，因为当前指代的是fast与slow中指代的不是相同颜色的球，所以slow的判断可以继续往下来搜索。
    • 主函数通过DFS+记忆化搜索+回溯的方式
      • 用set<pair<string,int>>的vis来存储对应的board字符串板子对应已经扔球的次数，来防止有重复的DFS过程发生
      • 对于每次的DFS过程都需要遍历当前的board的每一个位置以及当前手上的所有球，并且创建好新的插入球的板子nb并且进行Update过程，所得到的nb进入下一层的DFS过程，并且因为是&hand，记住要进行回溯操作，即在该层dfs结束后把扔进去的球重新加入到hand中。

以下是C++代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    int min_cnt = INT_MAX;
    set<pair<string, int> > vis;

    //△重点看一下这个面板的更新，消球的过程
    //快慢指针的使用
    void UpdateBoard(string& board) {
        //为了最后一次判断fast需要<=board.size()
        for (int slow = 0,fast = 0; fast <= board.size(); fast++) {
           if (fast < board.size() && board[slow] == board[fast]) continue;
           if (fast - slow >= 3) {
               board.erase(slow, fast - slow);
               fast = 0; //这里一定要重新从0索引开始寻找，因为可能会因为消球出现新的情况
           }
           slow = fast;
        }
    }

    //dfs+记忆化搜索的思路
    void DFS(string& board, string& hand, int cnt) {
        if (cnt >= min_cnt) return;
        if (vis.count({board, cnt})) return; //剪枝，这里要记下cnt的原因是同一个板子可能是经过了不同次数的插球导致的
        vis.insert({board, cnt}); //将板子对应其插球个数加入到记忆化set中
        if (board=="") {
            min_cnt = min(min_cnt, cnt); //找到了将球全部消除的次数，与当前最小次数取最小值
            return;
        }
        if (hand=="") return;
        int n = board.size(), m = hand.size();
        for (int i = 0; i <= n; ++i) { 
            for (int j = 0; j < m; ++j) {
                char ch = hand[j];
                hand.erase(hand.begin() + j); 
                //创建新的插入球后的板子
                string nb = board;
                nb.insert(nb.begin() + i, ch);
                UpdateBoard(nb);
                DFS(nb, hand, cnt + 1); //dfs过程
                hand.insert(hand.begin() + j, ch); //回溯
            }
        }
    }
    int findMinStep(string board, string hand) {
        DFS(board, hand, 0);
        return min_cnt == INT_MAX ? -1 : min_cnt;
    }
};

​