Flip Game II
设定一个游戏, 翻转字符串的任意++变成–, 问开始玩的人是否一定能赢.
这题就是记忆搜索的模板题, 用一个memo存字符串改变后的状态的答案, 然后按个找结果.
|
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 |
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; } } |