Friday, October 16, 2015

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 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.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    bool canWin(string s) {
        int n = s.size();
        for(int i=0; i<n-1; ++i){
            if(s.substr(i,2)=="++"){
                string tmp = s;
                tmp[i] = '-';
                tmp[i+1] = '-';
                if (!canWin(tmp)) return true;
            }
        }
        return false;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
//Java
class Solution {
    public boolean canWin(String s) {
        int n = s.length();
        for(int i=0; i<n-1; ++i){
            StringBuilder sb = new StringBuilder(s);
            if(sb.substring(i, i+2).equals("++")){
                sb.replace(i, i+2, "--");
                if(!canWin(sb.toString())) return true;
            }
        }
        return false;
    }
}

No comments:

Post a Comment