# Flip Game II

You are playing the following Flip Game with your friend: Given a string that contains only these two characters:`+`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.

Write a function to determine if the starting player can guarantee a win.

Example:

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

## Analysis

``````boolean canWinHelper(String s, HashMap<String, Boolean> map)
``````

``````             "++++" (T)
/       |       \
"--++" (T) "+--+" (F)  "++--" (T)
/                      \
"----" (F)                "----" (F)
``````

Time Complexity

DFS记忆化搜索时间复杂度近似：Big O

O(状态数*计算每个状态所需时间)

## Solution

Search + memoization (6ms 97.22%)

``````class Solution {
public boolean canWin(String s) {
char[] arr = s.toCharArray();
HashMap<String, Boolean> map = new HashMap<String, Boolean>();
return canWinHelper(s, map);
}

public boolean canWinHelper(String s, HashMap<String, Boolean> map) {
if (s == null || s.length() == 0) return false;
if (map.containsKey(s)) return map.get(s);
char[] arr = s.toCharArray();
boolean canWin = false;
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] == '+' && arr[i + 1] == '+') {
arr[i] = '-';
arr[i + 1] = '-';
boolean search = canWinHelper(new String(arr), map);
if (!search) {
canWin = true;
break;
}
arr[i] = '+';
arr[i + 1] = '+';
}
}
map.put(s, canWin);
return canWin;
}
}
``````

## Reference

https://mnmunknown.gitbooks.io/algorithm-notes/flip\_game.html

Time complexity estimation: https://www.jiuzhang.com/qa/1775/

https://www.jiuzhang.com/qa/6511/