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 <= 60currentState[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”.
-
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) }