Flip Game II

给一个string s, 包含’+’和’-‘, 给一个操作, 可以翻转++变成–, 两个人比赛, 看谁先不能翻转, 对方就赢了. 问你哪种setting可以保证先手的人必胜.

这个backtracking很好想, 就是假设call这个function的人是先手, 然后尝试所有的翻转, 如果不能翻就说明先手的人不能保证必胜.

public boolean canWin(String s) {
    for (int i = 0; i < s.length() - 1; ++i)
        if (s.charAt(i) == '+' && s.charAt(i + 1) == '+' && !canWin(s.substring(0, i) + "--" + s.substring(i + 2)))
                return true;
    return false;
}

这个是O(2^n)的解法

然后看到评论中有一个dp解法. 感觉面试不会考这个..既然是面试题….就没看..