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) }