## Flip Game II

• Time:O(3^{n / 2})
• Space:O(3^{n / 2})

## C++

``````class Solution {
public:
bool canWin(string currentState) {
if (memo.count(currentState))
return memo[currentState];

// if any of currentState[i:i + 2] == "++" and your friend can't win after
// changing currentState[i:i + 2] to "--" (or "-"), then you can win
for (int i = 0; i + 1 < currentState.length(); ++i)
if (currentState[i] == '+' && currentState[i + 1] == '+' &&
!canWin(currentState.substr(0, i) + '-' + currentState.substr(i + 2)))
return memo[currentState] = true;

return memo[currentState] = false;
}

private:
unordered_map<string, bool> memo;
};
``````

## JAVA

``````class Solution {
public boolean canWin(String currentState) {
if (memo.containsKey(currentState))
memo.get(currentState);

// if any of currentState[i:i + 2] == "++" and your friend can't win after
// changing currentState[i:i + 2] to "--" (or "-"), then you can win
for (int i = 0; i + 1 < currentState.length(); ++i)
if (currentState.charAt(i) == '+' && currentState.charAt(i + 1) == '+' &&
!canWin(currentState.substring(0, i) + "-" + currentState.substring(i + 2))) {
memo.put(currentState, true);
return true;
}

memo.put(currentState, false);
return false;
}

private Map<String, Boolean> memo = new HashMap<>();
}
``````

## Python

``````class Solution:
@lru_cache(None)
def canWin(self, currentState: str) -> bool:
# if any of currentState[i:i + 2] == "++" and your friend can't win after
# changing currentState[i:i + 2] to "--" (or "-"), then you can win
return any(True
for i, (a, b) in enumerate(zip(currentState, currentState[1:]))
if a == '+' and b == '+' and
not self.canWin(currentState[:i] + '-' + currentState[i + 2:]))
``````