Question

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

 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.

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

 Follow up:
    Derive your algorithm's runtime complexity.

Algorithm

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

Code

Java

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

// 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(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)

294 - Flip Game II

Question

Algorithm

Code

All Problems

All Solutions