Extremely efficient solution using Sprague-Grundy Theorem


  • 0
    
    class Solution(object):
        def _mex(self, A):
            x = 0
            while x in A:
                x += 1
            return x
        
        _basememo = {0: 0, 1: 0}
        def _base(self, N):
            #What is the grundy number of a row of N +'s?
            if N in Solution._basememo:
                return Solution._basememo[N]
            ans = self._mex(self._base(x) ^ self._base(N-2-x) for x in xrange(N-1))
            Solution._basememo[N] = ans
            return ans
            
        def canWin(self, S):
            from itertools import groupby
            piles = []
            for k, v in groupby(S, key = lambda x: x == '+'):
                if k:
                    u = len(list(v))
                    if u > 1:
                        piles.append(u)
            
            if not piles:
                return False
            grundy = reduce(lambda x, y: x ^ y, map(self._base, piles) )
            return bool(grundy)
    

Log in to reply
 

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