C++_Backtracking_Accepted


  • 1

    Updated: 146ms, 45.59%

    class Solution {
    public:
    bool canWin(string s) {
        int sign = 0;
        for(int i = 0; i < s.size(); ++i){
             if(s[i-1] == '+' && s[i] == '+'){
                sign = 1;
                s[i-1] = '-', s[i] = '-';
                if(!canWin(s)){return true;}//相手のターン, should be false;
                s[i-1] = '+', s[i] = '+';
            }
        }
        return false;
    }
    };
    

    First version: 32.60%, 172ms

    class Solution {
    public:
    bool canWin(string s) {
        int res = 0;
        win(s, res, 0, 1);
        return res == 1 ? true:false;
     }
    
    void win(string s, int& res, int turn, int start){
        //turn = even: オレのターン、 turn = odd: 相手のターン
        if(res == 1) return;
        int sign = 0;
        for(int i = start; i < s.size(); ++i){
             if(s[i-1] == '+' && s[i] == '+'){
                sign = 1;
                s[i-1] = '-', s[i] = '-';
                if(!canWin(s)){res = 1; return;}
                s[i-1] = '+', s[i] = '+';
            }
        }
        //if(res == 1) return;
        if(sign == 0 && turn % 2 != 0){res = 1;}
        return;
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.