Flip game ii

Math Dynamic Programming Backtracking Memoization Game Theory

52.3% acceptance

Mar 31, 2026

629

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn can_win(current_state: String) -> bool {
    use std::collections::HashMap;
    let mut memo: HashMap<String, bool> = HashMap::new();
    Self::dfs(&current_state, &mut memo)
  }

  fn dfs(state: &str, memo: &mut std::collections::HashMap<String, bool>) -> bool {
    if let Some(&res) = memo.get(state) { return res; }
    let bytes = state.as_bytes();
    for i in 0..bytes.len().saturating_sub(1) {
      if bytes[i] == b'+' && bytes[i + 1] == b'+' {
        let mut next = state.as_bytes().to_vec();
        next[i] = b'-';
        next[i + 1] = b'-';
        let next_str = unsafe { String::from_utf8_unchecked(next) };
        if !Self::dfs(&next_str, memo) {
          memo.insert(state.to_string(), true);
          return true;
        }
      }
    }
    memo.insert(state.to_string(), false);
    false
  }
}