Neat C++ code with DFS


  • 9
    U
    bool canWin(string s) {
        if (s.size() == 0) {
            return false;
        }
        
        bool isMoved = false;
        for (size_t i = 0; i < s.size() - 1; ++i) {
            if (s[i] == '+' && s[i + 1] == '+') {
                isMoved = true;
                s[i] = '-';
                s[i + 1] = '-';
                if (!canWin(s)) {
                    return true;
                }
                s[i] = '+';
                s[i + 1] = '+';
            }
        }
        
        if (!isMoved) {
            return false;
        }
    }

  • 1
    L

    It is a very nice solution! Thank you!


  • 0

    It is a very nice solution! Thank you!


  • 1
    H

    bool canWin(string s) {
    if (s.size() == 0) {
    return false;
    }

    for (size_t i = 0; i < s.size() - 1; ++i) {
        if (s[i] == '+' && s[i + 1] == '+') {
            s[i] = '-';
            s[i + 1] = '-';
            if (!canWin(s)) {
                return true;
            }
            s[i] = '+';
            s[i + 1] = '+';
        }
    }
    
    return false;
    

    }


  • 0
    This post is deleted!

  • 0

    Actually, you don't need the isMoved, and return false following for loop also works.


  • 0

    why you use ++i in this for loop? I tried i++, and it also works.


  • 0
    X

    what's the difference?


  • 0
    Z
    This post is deleted!

  • 0
    H
    
    bool canWin(string s) {
            for(int i = 1; i < s.size(); i++){
                if(s[i-1] == '+' && s[i] == '+'){
                    s[i-1] = '-'; s[i] = '-'; 
                    if(!canWin(s)) return !canWin(s);
                    s[i-1] = '+'; s[i] = '+';         
                }
            }
            
            return false;
        }

Log in to reply
 

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