BFS


  • 1

    Since the problem asks for minimum steps, it is natural to think of BFS which guarantees shortest path. We can just try all moves starting from the initial board.

        int findMinStep(string board, string hand) {
            unordered_map<char,int> ht;
            for(char c:hand) ht[c]++;
            queue<pair<string,unordered_map<char,int>>> q({make_pair(board,ht)});
            int step = 0;
            while(!q.empty()) {
                int n = q.size();
                step++;
                for(int i=0;i<n;i++) {
                    auto& p = q.front();
                    string bd = p.first;
                    for(int j=0;j<bd.size();j++) {
                        auto hnd = p.second;
                        if(!hnd[bd[j]]) continue;
                        hnd[bd[j]]--;
                        string bod = bd;
                        int rmv = rm(bod.insert(j,1,bd[j]),j);
                        if(rmv) j+=rmv-1;
                        if(bod.empty()) return step;
                        q.push(make_pair(bod,hnd));
                    }
                    q.pop();
                }
            }
            return -1;
        }
        int rm(string& board, int p) { //remove balls, return # of balls removed to the right of p
            int l = p-1, r = p+1;
            while(l>=0 && board[l]==board[p]) l--;
            while(r<board.size()&& board[r]==board[p]) r++;
            if(r-l>3) {
                l++;
                int rmv = rm(board.erase(l, r-l),l);
                return r-p-1+rmv;
            } else return 0;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.