293. Flip Game

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 twoconsecutive"++"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 compute all possible states of the string after one valid move.

For example, givens = "++++", after one move, it may become one of the following states:

[
  "--++",
  "+--+",
  "++--"
]

If there is no valid move, return an empty list[].

S：loop O(n)

    vector<string> generatePossibleNextMoves(string s) {
        vector<string> result;
        if (s.size() < 2) return vector<string>{};
        for (int i = 0; i < s.size() - 1; ++i) {
            if (s[i] == '+' && s[i + 1] == '+') {
                string str = s;
                str[i] = '-';
                str[i + 1] = '-';
                result.push_back(str);
            }
        }
        return result;
    }

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 twoconsecutive"++"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.

For example, givens = "++++", return true. The starting player can guarantee a win by flipping the middle"++"to become"+--+".

S：memorization time O(2^n) space O(2^n)

dfs，存储中间结果以供以后访问。最多有2^n种状态所以time和space complexity都为 O(2^n)？

class Solution {
public:
    bool canWin(string s) {
        if (s.size() < 2) return false;
        if (isWin.find(s) != isWin.end()) return isWin[s];
        for (int i = 0; i < s.size() - 1; ++i) {
            if (s[i] == '+' && s[i + 1] == '+') {
                string str = s;
                str[i] = '-';
                str[i + 1] = '-';
                if (!canWin(str)) {
                    isWin[s] = true;
                    return true;
                }
            }
        }
        isWin[s] = false;
        return false;
    }
private:
    unordered_map<string, bool> isWin;
};