# Python solution with detailed explanation

• Solution

Brute Force: Backtracking

1. Simple backtracking solution. This is O(N!). https://discuss.leetcode.com/topic/27282/theory-matters-from-backtracking-128ms-to-dp-0ms
2. Note that we reset the string before we test next_result. This is critical and failing this could result in bugs.
``````class Solution(object):
def helper(self, s):
for i in range(len(s)-1):
if s[i] == s[i+1] and s[i] == "+":
s[i] = s[i+1] = "-"
next_result = self.helper(s)
s[i] = s[i+1] = "+"
if next_result == False:
return True
return False

def canWin(self, s):
"""
:type s: str
:rtype: bool
"""
return self.helper([ch for ch in s])
``````

Memoization

• Throw in a cache.
``````class Solution(object):
def helper(self, s, cache):
cache_key = "".join(s)
if cache_key in cache:
return cache[cache_key]
for i in range(len(s)-1):
if s[i] == s[i+1] and s[i] == "+":
s[i] = s[i+1] = "-"
next_result = self.helper(s, cache)
s[i] = s[i+1] = "+"
if next_result == False:
cache[cache_key] = True
return True
cache[cache_key] = False
return cache[cache_key]

def canWin(self, s):
"""
:type s: str
:rtype: bool
"""
cache = {}
return self.helper([ch for ch in s], cache)
``````

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