# Python solution using DFS and memo(easy to follow)

• Try every feasible '++' to flip, If there is at least one choice that the opponent can't win. Return True. Using memo to cache.

``````class Solution(object):
def canWin(self, s):
"""
:type s: str
:rtype: bool
"""
self.memo = {}
return self.dfs(s)

def dfs(self, s):

if s not in self.memo:

if '++' not in s:
return False

res = []
for i in range(len(s)-1):
if s[i:i+2] == '++':
res.append(self.dfs(s[:i]+'--'+s[i+2:]))
self.memo[s] = not all(res) # if there is a False in res

return self.memo[s]
``````

Another version

``````class Solution(object):
def canWin(self, s):
"""
:type s: str
:rtype: bool
"""
self.memo = {}
return self.dfs(s)

def dfs(self, s):
if s not in self.memo:
if '++' not in s:  # base case
return False
for i in range(len(s)-1):
if s[i:i+2] == '++':
if not self.dfs(s[:i]+'--'+s[i+2:]): # if oppo can't win
self.memo[s] = True
return self.memo[s] # then return True
self.memo[s]=False  # tried every step still can't win
return self.memo[s]
``````

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