Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

294. Flip Game II

Time: $O(3^{n / 2})$

Space: $O(3^{n / 2})$

			


class Solution {
 public:
  bool canWin(string currentState) {
    if (memo.count(currentState))
      return memo[currentState];

    // If any of currentState[i:i + 2] == "++" and your friend can't win after
    // Changing currentState[i:i + 2] to "--" (or "-"), then you can win
    for (int i = 0; i + 1 < currentState.length(); ++i)
      if (currentState[i] == '+' && currentState[i + 1] == '+' &&
          !canWin(currentState.substr(0, i) + '-' + currentState.substr(i + 2)))
        return memo[currentState] = true;

    return memo[currentState] = false;
  }

 private:
  unordered_map<string, bool> memo;
};




			


class Solution {
  public boolean canWin(String currentState) {
    if (memo.containsKey(currentState))
      memo.get(currentState);

    // If any of currentState[i:i + 2] == "++" and your friend can't win after
    // Changing currentState[i:i + 2] to "--" (or "-"), then you can win
    for (int i = 0; i + 1 < currentState.length(); ++i)
      if (currentState.charAt(i) == '+' && currentState.charAt(i + 1) == '+' &&
          !canWin(currentState.substring(0, i) + "-" + currentState.substring(i + 2))) {
        memo.put(currentState, true);
        return true;
      }

    memo.put(currentState, false);
    return false;
  }

  private Map<String, Boolean> memo = new HashMap<>();
}




			


class Solution:
  @functools.lru_cache(None)
  def canWin(self, currentState: str) -> bool:
    # If any of currentState[i:i + 2] == "++" and your friend can't win after
    # Changing currentState[i:i + 2] to "--" (or "-"), then you can win
    return any(True
               for i, (a, b) in enumerate(zip(currentState, currentState[1:]))
               if a == '+' and b == '+' and
               not self.canWin(currentState[:i] + '-' + currentState[i + 2:]))