Leetcode 294 Flip Game II

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 twoconsecutive "++" 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.

Solution 1: DFS, complexity is O(n!), pay attention to the comments in below code

 public class Solution {  
   public boolean canWin(String s) {  
     char[] c=s.toCharArray();  
     return canWin(c);  
   }  
   private boolean canWin(char[] c) {  
     int n=c.length;  
     for (int i=1; i<n; i++) {  
       if (c[i-1]=='+' && c[i]=='+') {  
         c[i-1]='-'; c[i]='-';  
         boolean win=true;  
         if (canWin(c)) win=false;  
         c[i-1]='+';c[i]='+';  
         if (win) return true;//return must be after change back to '+'  
       }  
     }  
     return false;  
   }  
 }