294. 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 "+--+".
Follow up:
Derive your algorithm's runtime complexity.
这其实是一道图的问题，从初始值到最后的值。
每一个值是一个状态，状态之间用 flip 相连。
所以就是一个图遍历的问题。
如果我站在一个状态，如果这个状态找不到++或者我的下面的状态全是对方赢，这个状态肯定跪了。
时间复杂度是2^N 由分析state得出。

class Solution {
  public boolean canWin(String str) {
        Map<String, Boolean> mem = new HashMap<>();
        return helper(str, mem);
  }
  private boolean helper(String str, Map<String, Boolean> mem) {
    if (mem.containsKey(str)) return mem.get(str);
    List<String> nextMove = getNextMove(str);
    if (nextMove.size() == 0) {
        mem.put(str, false);
        return false;
       }
     for (String next : nextMove) {
        if (!helper(next, mem)) {
        mem.put(str, true);
        return true;
        }
      }
     mem.put(str, false);
     return false;
  }
  private List<String> getNextMove(String str) {
    List<String> ans = new ArrayList<>();
    for (int i = 0; i < str.length() - 1; i++) {
        if (str.substring(i, i + 2).equals("++")) {
              ans.add(str.substring(0, i) + "--" + str.substring(i + 2));
                }
        }
  return ans;
  }
}