he idea is try to replace every "++" in the current string s to "--" and see if the opponent can win or not, if the opponent cannot win, great, we win!
For the time complexity, here is what I thought, let's say the length of the input string s is n, there are at most n - 1 ways to replace "++" to "--" (imagine s is all "+++..."), once we replace one "++", there are at most (n - 2) - 1 ways to do the replacement, it's a little bit like solving the N-Queens problem, the time complexity is (n - 1) x (n - 3) x (n - 5) x ..., so it's O(n!!), double factorial.
Shawngbk
commented
7 years ago
he idea is try to replace every "++" in the current string s to "--" and see if the opponent can win or not, if the opponent cannot win, great, we win!
For the time complexity, here is what I thought, let's say the length of the input string s is n, there are at most n - 1 ways to replace "++" to "--" (imagine s is all "+++..."), once we replace one "++", there are at most (n - 2) - 1 ways to do the replacement, it's a little bit like solving the N-Queens problem, the time complexity is (n - 1) x (n - 3) x (n - 5) x ..., so it's O(n!!), double factorial.
public class Solution { public boolean canWin(String s) { if(s == null || s.length() < 2) return false; for(int i = 0; i < s.length()-1; i++) { if(s.charAt(i) == '+' && s.charAt(i+1) == '+') { String temp = s.substring(0, i) + "--" + s.substring(i+2, s.length()); //如果该方法不能执行，则证明先手获胜 if(!canWin(temp)) { return true; } } } return false; } }