the code passed 29 cases out of 33..I think a test case like "+++++++++" should be one which the start player can win(end up like "+--+--+--"), but OJ keeps saying that the player can't win in this case.
My approach is to, check the string from start to the end, for any position if it's "+" at that position and "+" at the following position, change these two position with "--", then check again. Until to the state where no further move can be made, we check if it's now starting player's turn or the second player's turn: to check this I use a variable named "flag", and at the start of each round if flag is even, it indicates that this is starting player's turn and vice versa. During this process if we ever find a state where no move can't be made and it's second player's turn, we return True;else we return False.
class Solution(object): def canWin(self,s): return self.helper(s,0) def helper(self,s,flag): if self.isValid(s)==False: if flag%2==0: return False return True res.append(s) for i in range(0,len(s)-1): if s[i]=="+" and s[i+1]=="+": newS=s[:i]+"--"+s[i+2:] if self.helper(newS,flag+1)==True: return True return False
9 pluses is indeed a losing state.
I'll denote the first player by A and the second player by B below.
If A takes two pluses at one end: --+++++++
B can then take the next two: ----+++++
Now, no matter whether A takes two pluses at the end or in the center, B can take two pluses and win.
If A takes two pluses leaving one at an end: +--++++++
The single plus at the end is now useless.
B can take the center two pluses in the center of the remaining six: +--++--++
Now there are two groups of double pluses; A takes one, B takes the other and wins.
If A takes two pluses leaving two at an end: ++--+++++
B can take the two at this end: ----+++++
And what follows is the same as situation (1).
If A takes two pluses leaving three at and end: +++--++++
B can take two pluses at the other end: +++--++--
Now A can either take two from the three at the beginning or the two in the center; B can take what A didn't and win.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.