# Question

Formatted question description: https://leetcode.ca/all/294.html

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 '-'.

# Algorithm

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

# Code

• 
public class Flip_Game_II {

public class Solution {
public boolean canWin(String s) {
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == '+' && s.charAt(i - 1) == '+') {

// can combine if, but leave it for clarity
if (!canWin(s.substring(0, i - 1) + "--" + s.substring(i + 1))) { // @note: after flip, opponent cannot win, then player can win
return true;
}
}
}

return false;
}
}
}

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

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;
}
}

• // OJ: https://leetcode.com/problems/flip-game-ii/
// Time: O(N!)
// Space: O(N!)
class Solution {
public:
bool canWin(string s) {
bitset<60> bs;
int cnt = 0;
int N = s.size();
for (int i = 0; i < N; ++i) {
if (s[i] == '+') {
bs.set(i);
++cnt;
}
}
unordered_map<bitset<60>, bool> m;
function<bool()> dp = [&]() {
if (cnt == 0 || cnt == 1) return false;
if (m.count(bs)) return m[bs];
bool ans = false;
for (int i = 0; i + 1 < N && !ans; ++i) {
if (bs.test(i) && bs.test(i + 1)) {
bs.reset(i);
bs.reset(i + 1);
cnt -= 2;
if (!dp()) ans = true;
bs.set(i);
bs.set(i + 1);
cnt += 2;
}
}
return m[bs] = ans;
};
return dp();
}
};

• 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
}