Concise 3ms C++ Solution


  • 5
    H

    At the first look, it is similar to Can I Win. But not like that problem, the board state is not relevant to the state of hand and this problem requires the minimum value. So, it seems that memorization might not help much. So, I just do it brute-force and stop iff it is sure there no better results than current one.

    Sort hand string so that we easily know if there at least 2 balls with same color in hand to eliminate a single ball on board. Refer to inline comments for details.

    According to the description, the number of balls in hand won't exceed 5, to make life easier, I just return a number equal or greater than 6 when there is no way to clear board.

    #define MAX_STEP 6 
    class Solution {
    public:
        int findMinStep(string board, string hand) {
            sort(hand.begin(), hand.end()); 
            int res = helper(board, hand); 
            return res > hand.size() ? -1 : res;
        }
        
        int helper(string b, string h) {
            if (b.empty()) return 0;
            if (h.empty()) return MAX_STEP;
            int res = MAX_STEP;
            for (int i = 0; i < h.size(); i++) {
                int j = 0;
                int n = b.size();
                while (j < n) {
                    int k = b.find(h[i], j);
                    if (k == string::npos) break;
                    if (k < n-1 && b[k] == b[k+1]) { // 2 consecutive balls with same color on board
                        string nextb = shrink(b.substr(0, k) + b.substr(k+2)); // shrink the string until no 3 or more consecutive balls in same color
                        if (nextb.empty()) return 1; // this is the best result for current board, no need to continue
                        string nexth = h;
                        nexth.erase(i, 1); // remove the used ball from hand
                        res = min(res, helper(nextb, nexth) + 1);
                        k++;
                    }
                    else if (i > 0 && h[i] == h[i-1]) { // 2 balls with same color in hand
                        string nextb = shrink(b.substr(0, k) + b.substr(k+1)); // shrink the string until no 3 or more consecutive balls in same color
                        if (nextb.empty()) return 2;  // this is the best result for current board, no need to continue
                        string nexth = h;
                        nexth.erase(i, 1); // remove the used balls from hand
                        nexth.erase(i-1, 1);
                        res = min(res, helper(nextb, nexth) + 2);
                    }
                    j = k + 1;
                }
            }
            return res;
        }
        
        string shrink(string s) {
            while(s.size() > 0) {
                int start = 0;
                bool done = true;
                for (int i = 0; i <= s.size(); i++) {
                    if (i == s.size() || s[i] != s[start]) {
                        if (i - start >= 3) {
                            s = s.substr(0, start) + s.substr(i);
                            done = false;
                            break;
                        }
                        start = i;
                    }
                }
                if (done) break;
            }
            return s;
        }
    };
    

  • 0

    Elegant solution! Thanks for sharing! : )


  • 1
    C

    You can just record res during the search, and just return immediately if the number of balls used is more than res. This may reduce time a lot, I think.
    By the way, brilliant solution!


Log in to reply
 

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