Welcome to Subscribe On Youtube

294. Flip Game II

Description

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.

Solutions

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

• Java
• C++
• Python
• Go

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

• using ll = long long;
  
  class Solution {
  public:
      int n;
      unordered_map<ll, bool> memo;
  
      bool canWin(string currentState) {
          n = currentState.size();
          ll mask = 0;
          for (int i = 0; i < n; ++i)
              if (currentState[i] == '+') mask |= 1ll << i;
          return dfs(mask);
      }
  
      bool dfs(ll mask) {
          if (memo.count(mask)) return memo[mask];
          for (int i = 0; i < n - 1; ++i) {
              if ((mask & (1ll << i)) == 0 || (mask & (1ll << (i + 1))) == 0) continue;
              if (dfs(mask ^ (1ll << i) ^ (1ll << (i + 1)))) continue;
              memo[mask] = true;
              return true;
          }
          memo[mask] = false;
          return false;
      }
  };
  

• 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