Flip Game II

设定一个游戏, 翻转字符串的任意++变成–, 问开始玩的人是否一定能赢.

这题就是记忆搜索的模板题, 用一个memo存字符串改变后的状态的答案, 然后按个找结果.

class Solution {
    public boolean canWin(String s) {
        Map<String, Boolean> memo = new HashMap<>();
        find(s, memo);
        return memo.get(s);
    }
    boolean find(String s, Map<String, Boolean> memo){
        if(memo.containsKey(s))
            return memo.get(s);
        Boolean res = false;
        for(int i = 0; i < s.length(); i++) {
            if(i > 0 && s.charAt(i) == '+' && s.charAt(i - 1) == '+'){
                StringBuffer sb = new StringBuffer(s);
                sb.setCharAt(i - 1, '-');
                sb.setCharAt(i, '-');
                if(!find(sb.toString(),memo)){
                    res = true;
                    break;
                }
            }
        }
        memo.put(s, res);
        return res;
    }
}