You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.
Write a function to determine if the starting player can guarantee a win.
Example:
Input: s = "++++"
Output: true
Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".
Follow up:
Derive your algorithm's runtime complexity.
這其實(shí)是一道圖的問題，從初始值到最后的值东涡。
每一個(gè)值是一個(gè)狀態(tài)倘待，狀態(tài)之間用 flip 相連凸舵。
所以就是一個(gè)圖遍歷的問題。
如果我站在一個(gè)狀態(tài)啊奄，如果這個(gè)狀態(tài)找不到++或者我的下面的狀態(tài)全是對(duì)方贏菇夸，這個(gè)狀態(tài)肯定跪了。
時(shí)間復(fù)雜度是2^N 由分析state得出鞠眉。
class Solution {
public boolean canWin(String str) {
Map<String, Boolean> mem = new HashMap<>();
return helper(str, mem);
}
private boolean helper(String str, Map<String, Boolean> mem) {
if (mem.containsKey(str)) return mem.get(str);
List<String> nextMove = getNextMove(str);
if (nextMove.size() == 0) {
mem.put(str, false);
return false;
}
for (String next : nextMove) {
if (!helper(next, mem)) {
mem.put(str, true);
return true;
}
}
mem.put(str, false);
return false;
}
private List<String> getNextMove(String str) {
List<String> ans = new ArrayList<>();
for (int i = 0; i < str.length() - 1; i++) {
if (str.substring(i, i + 2).equals("++")) {
ans.add(str.substring(0, i) + "--" + str.substring(i + 2));
}
}
return ans;
}
}
