294. Flip Game II - cocoder39/coco39_LC GitHub Wiki

294. Flip Game II

follow up of flip game

time complexity reference

t(n) = n + (n - 2) * n + (n - 2) * (n - 2) * (n - 4) * n... = (1 + n-2 + (n-2)(n-4)) * n!! = 2 * n!! = O(n!!), space complexity is large since each call would copy the string, optimize it by passing reference

bool canWin(string s) {
        for (int i = 0; i < (int)s.length() - 1; i++) {
            if (s[i] == '+' && s[i + 1] == '+') {
                s[i] = '-';
                s[i + 1] = '-';
                if (! canWin(s))
                    return true;
                s[i] = '+';
                s[i + 1] = '+';
            }
        }
        return false;
    }

class Solution {
public:
    bool canWin(string s) {
        string copy = s;
        bool res = helper(copy);
        return res;
    }
private:
    bool helper(string& s) {
        for (int i = 0; i + 1 < s.length(); i++) {
            if (s[i] == '+' && s[i + 1] == '+') {
                s[i] = '-';
                s[i + 1] = '-';
                bool res = helper(s);
                s[i] = '+';
                s[i + 1] = '+';
                if (! res)   return true;
            }
        }
        return false;
    }
};

now space complexity is the depth of call stack, which is O(n). attention to the implementation. the implementation below would return wrong answer. This is because return true is not the end of the program. if return true at the other guy's turn, the program would go on, thus s should be recovered before return.

bool helper(string& s) {
        for (int i = 0; i + 1 < s.length(); i++) {
            if (s[i] == '+' && s[i + 1] == '+') {
                s[i] = '-';
                s[i + 1] = '-';
                if (! helper(s) return true;
                s[i] = '+';
                s[i + 1] = '+';
            }
        }
        return false;
    }