# 294. Flip Game II

## Description

You are playing a Flip Game with your friend.

You are given a string currentState that contains only '+' and '-'. You and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move, and therefore the other person will be the winner.

Return true if the starting player can guarantee a win, and false otherwise.

Example 1:

Input: currentState = "++++"
Output: true
Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".


Example 2:

Input: currentState = "+"
Output: false


Constraints:

• 1 <= currentState.length <= 60
• currentState[i] is either '+' or '-'.

## Solutions

The function canWin means: “In the current state, there is at least one possible option that can make him/her win”.

• class Solution {
private int n;
private Map<Long, Boolean> memo = new HashMap<>();

public boolean canWin(String currentState) {
n = currentState.length();
for (int i = 0; i < n; ++i) {
if (currentState.charAt(i) == '+') {
}
}
}

}
for (int i = 0; i < n - 1; ++i) {
if ((mask & (1 << i)) == 0 || (mask & (1 << (i + 1))) == 0) {
continue;
}
if (dfs(mask ^ (1 << i) ^ (1 << (i + 1)))) {
continue;
}
return true;
}
return false;
}
}

• using ll = long long;

class Solution {
public:
int n;
unordered_map<ll, bool> memo;

bool canWin(string currentState) {
n = currentState.size();
for (int i = 0; i < n; ++i)
if (currentState[i] == '+') mask |= 1ll << i;
}

for (int i = 0; i < n - 1; ++i) {
if ((mask & (1ll << i)) == 0 || (mask & (1ll << (i + 1))) == 0) continue;
if (dfs(mask ^ (1ll << i) ^ (1ll << (i + 1)))) continue;
return true;
}
return false;
}
};

• class Solution:
def canWin(self, s: str) -> bool:
for i in range(0, len(s) - 1):
if s[i:i + 2] == "++":
if not self.canWin(s[:i] + "--" + s[i + 2:])
# Note: after flip, opponent cannot win, then player can win
return True
return False

#############

class Solution:
def canWin(self, s: str) -> bool:
for i in range(1, len(s)):
if s[i] == '+' and s[i - 1] == '+':
if not self.canWin(s[:i - 1] + "--" + s[i + 1:]):
# Note: after flip, opponent cannot win, then player can win
return True
return False

#############

'''
big-O analysis: (N^2)

'''
class Solution:
def canWin(self, currentState: str) -> bool:
@cache
for i in range(n - 1):
if (mask & (1 << i)) == 0 or (mask & (1 << (i + 1)) == 0):
continue
if dfs(mask ^ (1 << i) ^ (1 << (i + 1))):
continue
return True
return False

for i, c in enumerate(currentState):
if c == '+':

############

'''
big-O analysis: (N!)

'''
class Solution(object):
def canWin(self, s):
"""
:type s: str
:rtype: bool
"""

def helper(s, visited):
if s in visited:
return visited[s]

visited[s] = False
for i in range(0, len(s) - 1):
if s[i] + s[i + 1] == "++":
if helper(s[:i] + "--" + s[i + 2:], visited) == False:
visited[s] = True
return visited[s]

visited = {}
return helper(s, visited)


• func canWin(currentState string) bool {
n := len(currentState)
memo := map[int]bool{}
for i, c := range currentState {
if c == '+' {
}
}
var dfs func(int) bool
dfs = func(mask int) bool {
if v, ok := memo[mask]; ok {
return v
}
for i := 0; i < n-1; i++ {
continue
}
if dfs(mask ^ (1 << i) ^ (1 << (i + 1))) {
continue
}