lc294-Flip Game II

發表於   |   分類於   |   0 comments   |  

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.

For example, given s = “++++”, return true. The starting player can guarantee a win by flipping the middle “++” to become “+–+”.

一开始写的算法是只要能赢就返回true，但题意是guarantee，即对手无论如何下都能保证赢。无奈刚过subscription时间，无法提交验证他们提供的test cases。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    unordered_map<string, bool> mp;
    bool canWin(string s) {
        if (mp.count(s)) return mp[s];
        int l = s.length();
        
        for (int i = 0; i < l-1; i++) {
            if (s[i] == '+' && s[i+1] == '+') {
                s[i] = '-';
                s[i+1] = '-';
                bool not_found = true;
                for (int j = 0; j < l-1; j++) {
                    if (s[j] == '+' && s[j+1] == '+') {
                        s[j] = '-';
                        s[j+1] = '-';
                        if (!canWin(s)) not_found = false;
                        s[j] = '+';
                        s[j+1] = '+';
                    }
                }
                mp[s] = not_found;
                if (not_found) {return true;}
                s[i] = '+';
                s[i+1] = '+';
            }
        }
        mp[s] = false;
        return false;
    }
};

discussion里有更简洁的做法，在每次canWin里只考虑一方是否能赢，而不是先手下完再用一个循环考虑后手，两步之后再递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    unordered_map<string, bool> mp;
public:
    bool canWin(string s) {
        if(mp.count(s)) return mp[s];
        if(s.length() < 2) return false;
        for(int i=1; i<s.length(); i++){
            if(s[i-1] == '+' && s[i] == '+'){
                string t = s;
                t[i-1] = t[i] = '-';
                if(!canWin(t)){
                    mp[s] = true;
                    return true;
                }
                //s[i-1] = s[i] = '+';
            }
        }
        mp[s] = false;
        return false;
    }
};

(ref: https://discuss.leetcode.com/topic/63191/c-backtracking-with-memorization-26ms)