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;
}
}