C++, with memoization, not using string manip


  • 0
    A

    This solution turns out to be a bit unwieldy, since vectors in C++ are more difficult to handle than strings.

    class Solution {
    public:
        map<vector<int>, bool> memo = {};
        
        static bool wayToSort(int i, int j) { return i > j; }
        
        vector<int> vectorize(string s) {
            vector<int> v {};
            int runLength = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s[i] == '+') {
                    runLength++;
                } 
                if (i+1 == s.size() || s[i+1] == '-') {
                    if (runLength >= 2) v.push_back(runLength);
                    runLength = 0;
                }
            }
            sort(v.begin(), v.end(), wayToSort);
            return v;
        }
    
        bool canWinImpl(vector<int> v) {
            if (v.empty()) return false;
        
            auto s = memo.find(v);
            if (s != memo.end()) { // We already have the answer in our memoization map
                return s->second;
            }
            
            for (int j = 0; j < v.size(); j++) {
                for (int subGameA = 0; subGameA < v[j] / 2; subGameA++) {
                    auto w = vector<int>(v); // Copy the original vector
                    w.erase(w.begin()+j); // Remove the original subgame
                    int subGameB = v[j] - subGameA - 2;
                    // If the remaining subgames are still valid, push them to the vector
                    if (subGameA >= 2) w.push_back(subGameA);
                    if (subGameB >= 2) w.push_back(subGameB);
                    sort(w.begin(), w.end(), wayToSort); // ensure that all equivalent memos are mapped to the same vector
                    if (!canWinImpl(w)) { // We made our move; if the opponent can't win, then we win
                        memo[v] = true;
                        return true;
                    }
                }
            }
            
            // None of the available moves resulted in a win. We lose given this memo.
            memo[v] = false;
            return false;
        }
            
        bool canWin(string s) {
            return canWinImpl(vectorize(s));
        }
    };

Log in to reply
 

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