294. Flip Game II

back tracking with memorization

class Solution {
public:
    bool canWin(string s) {
        if (s.size() < 2) return false;
        if (states.count(s)) return states[s];
        states[s] = false;
        for (int i = 0; i < s.size() - 1; i++) 
          if (s[i] == '+' && s[i + 1] == '+') {
            s[i] = s[i + 1] = '-';
            if (!canWin(s)) {
                s[i] = s[i + 1] = '+';
                states[s] = true;
                break;
            }
            s[i] = s[i + 1] = '+';
        }
        return states[s];
    }
private:
    unordered_map<string, bool> states;
};

using game theory can quite understand

class Solution {
public:
    int firstMissingNumber(unordered_set<int> lut) {
        int m = lut.size();
  // for (auto &i:lut)cout<<i<<' ';cout<<endl;
        for (int i = 0; i < m; ++i) {
            if (lut.count(i) == 0) return i;
        }
        return m;
//        return lut.count(0) == 1;
    }

    bool canWin(string s) {
        int curlen = 0, maxlen = 0;
        vector<int> board_init_state;
        for (int i = 0; i < s.size(); ++i) {    
            if (s[i] == '+') curlen++;              // Find the length of all continuous '+' signs
            if (i+1 == s.size() || s[i] == '-') {
                if (curlen >= 2) board_init_state.push_back(curlen);    // only length >= 2 counts
                maxlen = max(maxlen, curlen);       // Also get the maximum continuous length
                curlen = 0;
            }
        }          // For instance ++--+--++++-+ will be represented as (2, 4)
        vector<int> g(maxlen+1, 0);    // Sprague-Grundy function of 0 ~ maxlen
        for (int len = 2; len <= maxlen; ++len) {
            cout<<endl<<len<<":"<<endl;
            unordered_set<int> gsub;    // the S-G value of all subgame states
            for (int len_first_game = 0; len_first_game < len/2; ++len_first_game) {
                int len_second_game = len - len_first_game - 2;
                cout<<len_first_game<<' '<<len_second_game<<' '<<(g[len_first_game] ^ g[len_second_game])<<endl;
                // Theorem 2: g[game] = g[subgame1]^g[subgame2]^g[subgame3]...;
                gsub.insert(g[len_first_game] ^ g[len_second_game]);
            }
            g[len] = firstMissingNumber(gsub);
        }

        for (int i = 0; i <= maxlen; i++) cout<<g[i]<<' ';cout<<endl;

        int g_final = 0;
        for (auto& s: board_init_state) g_final ^= g[s];
        return g_final != 0;    // Theorem 1: First player must win iff g(current_state) != 0
    }
};