294. Flip Game II

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + 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.

Write a function to determine if the starting player can guarantee a win.

Example:

Input: s = "++++"
Output: true 
Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".

Follow up:
Derive your algorithm's runtime complexity.

Rust Solution

struct Solution;
use std::collections::HashMap;

impl Solution {
    fn can_win(s: String) -> bool {
        let mut s: Vec<char> = s.chars().collect();
        let n = s.len();
        if n == 0 {
            return false;
        }
        let mut memo: HashMap<Vec<char>, bool> = HashMap::new();
        Self::dp(&mut s, &mut memo, n)
    }
    fn dp(s: &mut Vec<char>, memo: &mut HashMap<Vec<char>, bool>, n: usize) -> bool {
        if let Some(&res) = memo.get(s) {
            return res;
        }
        let mut res = false;
        for i in 0..n - 1 {
            if res {
                break;
            }
            if s[i] == '+' && s[i + 1] == '+' {
                s[i] = '-';
                s[i + 1] = '-';
                res |= !Self::dp(s, memo, n);
                s[i] = '+';
                s[i + 1] = '+';
            }
        }
        memo.insert(s.to_vec(), res);
        res
    }
}

#[test]
fn test() {
    let s = "++++".to_string();
    let res = true;
    assert_eq!(Solution::can_win(s), res);
}

Having problems with this solution? Click here to submit an issue on github.