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.

The idea is try to replace every "++" in the current string s to "--" and see if the opponent has the chance to win or not, if the opponent is guaranteed to lose, 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'sO(n!!), .

1 public class Solution { 2     public boolean canWin(String s) { 3         if (s==null || s.length()<=1) return false; 4         for (int i=0; i

 

Better Solution:  (205ms -> 19ms)

 but the time complexity of the backtracking method is high. During the process of searching, we could encounter duplicate computation as the following simple case.

One search path:

Input s = "++++++++"

Player 0: "--++++++"

Player 1: "----++++"

Player 0: "----+--+"

Player0 can win for the input string as "----++++".

Another search path:

Player 0: "++--++++"

Player 1: "----++++"

Player 0: "----+--+"

(Duplicate computation happens. We have already known anyone can win for the

input string as "----++++".)

Use a HashMap to avoid duplicate computation

Key : InputString.

Value: can win or not.

1 public boolean canWin(String s) { 2     if (s == null || s.length() < 2) { 3         return false; 4     } 5     HashMap
     
       winMap = new HashMap
      
       (); 6     return helper(s, winMap); 7 } 8  9 public boolean helper(String s, HashMap
       
         winMap) {10     if (winMap.containsKey(s)) {11         return winMap.get(s);12     }13     for (int i = 0; i < s.length() - 1; i++) {14         if (s.startsWith("++", i)) {15             String t = s.substring(0, i) + "--" + s.substring(i+2);16             if (!helper(t, winMap)) {17                 winMap.put(s, true);18                 return true;19             }20         }21     }22     winMap.put(s, false);23     return false;24 }
       
      
     

 Reference: