Welcome to Subscribe On Youtube

Question

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

You are playing a Flip Game with your friend.

You are given a string currentState that contains only '+' 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.

Return true if the starting player can guarantee a win, and false otherwise.

 

Example 1:

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

Example 2:

Input: currentState = "+"
Output: false

 

Constraints:

  • 1 <= currentState.length <= 60
  • currentState[i] is either '+' or '-'.

 

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

  • 
    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;
            }
        }
    }
    
    ############
    
    class Solution {
        private int n;
        private Map<Long, Boolean> memo = new HashMap<>();
    
        public boolean canWin(String currentState) {
            long mask = 0;
            n = currentState.length();
            for (int i = 0; i < n; ++i) {
                if (currentState.charAt(i) == '+') {
                    mask |= 1 << i;
                }
            }
            return dfs(mask);
        }
    
        private boolean dfs(long mask) {
            if (memo.containsKey(mask)) {
                return memo.get(mask);
            }
            for (int i = 0; i < n - 1; ++i) {
                if ((mask & (1 << i)) == 0 || (mask & (1 << (i + 1))) == 0) {
                    continue;
                }
                if (dfs(mask ^ (1 << i) ^ (1 << (i + 1)))) {
                    continue;
                }
                memo.put(mask, true);
                return true;
            }
            memo.put(mask, false);
            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:
        def canWin(self, s: str) -> bool:
            for i in range(0, len(s) - 1):
                if s[i:i + 2] == "++":
                    if not self.canWin(s[:i] + "--" + s[i + 2:])
                        # Note: after flip, opponent cannot win, then player can win
                        return True
            return False
    
    
    class Solution:
        def canWin(self, s: str) -> bool:
            for i in range(1, len(s)):
                if s[i] == '+' and s[i - 1] == '+':
                    if not self.canWin(s[:i - 1] + "--" + s[i + 1:]):
                        # Note: after flip, opponent cannot win, then player can win
                        return True
            return False
    
    #############
    
    '''
    big-O analysis: (N^2)
    
    '''
    class Solution:
        def canWin(self, currentState: str) -> bool:
            @cache
            def dfs(mask):
                for i in range(n - 1):
                    if (mask & (1 << i)) == 0 or (mask & (1 << (i + 1)) == 0):
                        continue
                    if dfs(mask ^ (1 << i) ^ (1 << (i + 1))):
                        continue
                    return True
                return False
    
            mask, n = 0, len(currentState)
            for i, c in enumerate(currentState):
                if c == '+':
                    mask |= 1 << i
            return dfs(mask)
    
    ############
    
    '''
    big-O analysis: (N!)
    
    '''
    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)
    
    
  • func canWin(currentState string) bool {
    	n := len(currentState)
    	memo := map[int]bool{}
    	mask := 0
    	for i, c := range currentState {
    		if c == '+' {
    			mask |= 1 << i
    		}
    	}
    	var dfs func(int) bool
    	dfs = func(mask int) bool {
    		if v, ok := memo[mask]; ok {
    			return v
    		}
    		for i := 0; i < n-1; i++ {
    			if (mask&(1<<i)) == 0 || (mask&(1<<(i+1))) == 0 {
    				continue
    			}
    			if dfs(mask ^ (1 << i) ^ (1 << (i + 1))) {
    				continue
    			}
    			memo[mask] = true
    			return true
    		}
    		memo[mask] = false
    		return false
    	}
    	return dfs(mask)
    }
    

All Problems

All Solutions