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

294 - Flip Game II

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions