Just Backtracking - implement using std::list c++ (12ms)


  • 0
    A

    The idea is to represent all the 2 or more continuous '+' using a list.

    bool canWin(list<int>& groups) {
        if (groups.empty()) return false;
        
        bool canW = false;
        for (auto it = groups.begin(); it != groups.end(); ++it) {
            int interval = *it;
            it = groups.erase(it);
            int newInterval = interval - 2;
            for (int left = 0; left <= newInterval / 2; ++left) {
                int right = newInterval - left;
                if (left >= 2) it = groups.insert(it, left);
                if (right >= 2) it = groups.insert(it, right);
                if (!canWin(groups)) canW = true;
                if (right >= 2) it = groups.erase(it);
                if (left >= 2) it = groups.erase(it);
                if (canW) break;
            } // for
            it = groups.insert(it, interval);
            if (canW) return true;
        } // for
        return false;
    } // canWin
    
    bool canWin(string s) {
        list<int> groups;
        int start = 0, end = 0;
        while (start < s.size() && end < s.size()) {
            while (s[start] == '-') start++;
            end = start;
            while (end < s.size() && s[end] == '+') end++;
            if (end - start >= 2) groups.push_back(end - start);
            start = end;
        } // while
        
        return canWin(groups);
    }

Log in to reply
 

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