2.4 Flip Game II
Description
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.
For example, given s = "++++", return true. The starting player can guarantee a win by flipping the middle "++" to become "+--+".
Follow up: Derive your algorithm's runtime complexity.
Method
one : DFS , Backtracking
For loop each step that a start can flip, and then use the remain string as the entry of next game, reverse res 0 if next level return true it means another one win, then go to next steps, or if return false, it means that next one fail, the person who move at this time win. 1 it moves by another person, it he win then return true, other wise false.
2 :
Time and Space Complexity
- n!! T(N) = (N-2) T(N-2) = (N-2) (N-4) T(N-4) ... = (N-2) (N-4) (N-6) ... ~ O(N!!)
- dp + memory
Code
public class Solution { public boolean canWin(String s) { if (s == null || s.length() == 0){ return false; } for (int i = 0; i < s.length(); i++){ if (s.startsWith("++", i)){ String t = s.substring(0, i) + "--" + s.substring(i + 2); if (!canWin(t)){ return true; } } } return false;
}
}