[LintCode] Problem 913 - Flip Game II

Posted on | In ,

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

No.1

Input: s = “++++”

Output: true

Explanation:
The starting player can guarantee a win by flipping the middle “++” to become “+–+”.

No.2

Input: s = “+++++”

Output: false

Explanation:
The starting player can not win
“+++–” –> “+—-“
“++–+” –> “—-+”

Challenge

Derive your algorithm’s runtime complexity.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private Map<String, Boolean> map = new HashMap<>();

public boolean canWin(String s) {
    if (map.containsKey(s))
        return map.get(s);

    int idx = s.indexOf("++", 0);

    while (idx != -1) {
        String str = s.substring(0, idx) + "--" + s.substring(idx + 2);

        if (!canWin(str)) {
            map.put(str, false);
            return true;
        }

        map.put(str, true);
        idx = s.indexOf("++", idx + 1);
    }

    return false;
}