O(n)-time O(1)-space C++ solution


  • 0

    The algorithm is proposed in:

    https://leetcode.com/discuss/64344/theory-matters-from-backtracking-128ms-to-dp-0ms
    

    Complexities:

    • Time: O(n)

    • Space: O(1)

    C++ Code:

    bool canWin(string s) {
        // Get the primary part of g[n], time complexity O(1)
        int NOPERIOD_LAST = 87;
        int PERIOD = 34;
        vector<int> g(NOPERIOD_LAST, 0);
        vector<bool> fmv(NOPERIOD_LAST, true);
        for (int idx = 2; idx < NOPERIOD_LAST; ++idx) {
            fill_n(fmv.begin(), idx, true);
            for (int first = 0, last = idx - 2; first <= last; ++first, --last) {
                fmv[g[first] ^ g[last]] = false;
            }
            g[idx] = find(fmv.begin(), fmv.end(), true) - fmv.begin();
        }
    
        // Get g[length of '+...+'] and xor them together: O(n)
        int result = 0;
        for (string::iterator first = s.begin(); first != s.end(); ++first) {
            if (*first == '+') {
                // linear search to find the length of successive '+', time O(last-first)
                string::iterator last = find(first, s.end(), '-'); 
                size_t dist = last - first;
    
                // calculate g[dist]. Note that the time of for-loop is O(last-first)
                for (; dist >= NOPERIOD_LAST; dist -= PERIOD);
                result ^= g[dist];
    
                // update first, skip (last-first) entries
                if (last == s.end()) {
                    break;
                }
                else {
                    first = last;
                }           
            }
        }
        return static_cast<bool>(result);
    }

  • 0
    M

    What are the magic numbers 34 and 87?


  • 0

    @maigo The sequence g[n], also shown in https://oeis.org/A215721 , has a period of 34 after its first 87 elements.


Log in to reply
 

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