A solution using SG beats 100%


  • 0
    M

    Similar with Nim game, we can think that continuous '+' together is one pile of stones.
    Then using https://www.wikiwand.com/en/Sprague–Grundy_theorem and memorization, we can find the answer.

    class Solution(object):
        sg = {0: 0, 1: 0, 2: 1}
        def get_sg(self, n):
            if n in self.sg:
                return self.sg[n]
            vis = set()
            i = 0
            while i <= n - 2 - i:
                vis.add(self.get_sg(n - 2 - i) ^ self.get_sg(i))
                i += 1
            i = 0
            while i in vis:
                i += 1
            self.sg[n] = i
            return i
                
            
        def canWin(self, s):
            """
            :type s: str
            :rtype: bool
            """
            res = 0
            for i in s.split('-'):
                res ^= self.get_sg(len(i))
            return res > 0
    
            
    

Log in to reply
 

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