Skip to content

294. Flip Game II 👍

  • Time: $O(3^{n / 2})$
  • Space: $O(3^{n / 2})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  bool canWin(string currentState) {
    const auto it = mem.find(currentState);
    if (it == mem.cend())
      return it->second;

    // 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 mem[currentState] = true;

    return mem[currentState] = false;
  }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public boolean canWin(String currentState) {
    if (mem.containsKey(currentState))
      mem.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))) {
        mem.put(currentState, true);
        return true;
      }

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

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

1
2
3
4
5
6
7
8
9
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:]))