294. Flip Game II

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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.

Code

class Solution {
    public boolean canWin(String s) {
        for(int i = 1; i < s.length(); i++){
            if(s.charAt(i) == '+' && s.charAt(i - 1) == '+'){
                char[] arr = s.toCharArray();
                arr[i] = '-';
                arr[i - 1] = '-';
                if(!canWin(new String(arr))){
                    return true;
                }
            }
        }
        
        return false;
    }
}

class Solution:
    def canWin(self, s: str) -> bool:
        for i in range(len(s) - 1):
            if s[i] == '+' and s[i + 1] == '+':
                # 对手不能赢的情况下
                if not self.canWin(s[:i] + "--" + s[i + 2:]):
                    return True
        # 没有能赢的情况
        return False