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
Solution 1
The function canWin means: “In the current state, there is at least one possible option that can make him/her win”.
Solution 2
The Sprague-Grundy theorem defines a Sprague-Grundy number (SG number for short) for each state of the game. The combination of game states is equivalent to the XOR operation of the SG number.
The complete statement of the Sprague-Grundy theorem is as follows:
If a game meets the following conditions:
- Two-player, turn-based
- Full disclosure of information
- No random factors
- It must end within a limited number of steps, and the number of moves per step is limited.
- No ties
- Both sides have the same actions and victory goals.
- The goal of victory is to achieve the final state by yourself, or the one who takes the last step wins (normal play)
| Then each state in the game can be assigned a non-negative integer, called the Sprague-Grundy number, according to the following rules, namely $SG(A)=mex{SG(B) | A->B}$. (In the formula, $A$, $B$ represents the state, which means that the $A$ state can reach the $B$ state after one step of action, and $mex$ represents the smallest non-negative integer not included in a set) |
SG numbers have the following properties:
- When the SG number is 0, the second player will win; when the SG number is positive, the first player will win;
- If a parent state can be split into multiple independent sub-states, then the SG number of the parent state is equal to the XOR of the SG number of each sub-state.
References: How did the Sprague-Grundy theorem come up
Time complexity $O(n^2)$.
-
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; } } // Solution 2 class Solution { private int n; private int[] sg; public boolean canWin(String currentState) { n = currentState.length(); sg = new int[n + 1]; Arrays.fill(sg, -1); int i = 0; int ans = 0; while (i < n) { int j = i; while (j < n && currentState.charAt(j) == '+') { ++j; } ans ^= win(j - i); i = j + 1; } return ans > 0; } private int win(int i) { if (sg[i] != -1) { return sg[i]; } boolean[] vis = new boolean[n]; for (int j = 0; j < i - 1; ++j) { vis[win(j) ^ win(i - j - 2)] = true; } for (int j = 0; j < n; ++j) { if (!vis[j]) { sg[i] = j; return j; } } return 0; } } -
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; } }; // Solution 2 class Solution { public: bool canWin(string currentState) { int n = currentState.size(); vector<int> sg(n + 1, -1); sg[0] = 0, sg[1] = 0; function<int(int)> win = [&](int i) { if (sg[i] != -1) return sg[i]; vector<bool> vis(n); for (int j = 0; j < i - 1; ++j) vis[win(j) ^ win(i - j - 2)] = true; for (int j = 0; j < n; ++j) if (!vis[j]) return sg[i] = j; return 0; }; int ans = 0, i = 0; while (i < n) { int j = i; while (j < n && currentState[j] == '+') ++j; ans ^= win(j - i); i = j + 1; } return ans > 0; } }; -
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) # Solution 2 class Solution: def canWin(self, currentState: str) -> bool: def win(i): if sg[i] != -1: return sg[i] vis = [False] * n for j in range(i - 1): vis[win(j) ^ win(i - j - 2)] = True for j in range(n): if not vis[j]: sg[i] = j return j return 0 n = len(currentState) sg = [-1] * (n + 1) sg[0] = sg[1] = 0 ans = i = 0 while i < n: j = i while j < n and currentState[j] == '+': j += 1 ans ^= win(j - i) i = j + 1 return ans > 0 -
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) } // Solution 2 func canWin(currentState string) bool { n := len(currentState) sg := make([]int, n+1) for i := range sg { sg[i] = -1 } var win func(i int) int win = func(i int) int { if sg[i] != -1 { return sg[i] } vis := make([]bool, n) for j := 0; j < i-1; j++ { vis[win(j)^win(i-j-2)] = true } for j := 0; j < n; j++ { if !vis[j] { sg[i] = j return j } } return 0 } ans, i := 0, 0 for i < n { j := i for j < n && currentState[j] == '+' { j++ } ans ^= win(j - i) i = j + 1 } return ans > 0 }