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)
    
    

All Problems

All Solutions