C++ backtracking with memorization (26ms)


  • 0
    S

    As topic:

    class Solution {
        unordered_map<string, bool> mp;
    public:
        bool canWin(string s) {
    
            if(mp.count(s)) return mp[s];
            if(s.length() < 2) return false;
            for(int i=1; i<s.length(); i++){
                if(s[i-1] == '+' && s[i] == '+'){
                    string t = s;
                    t[i-1] = t[i] = '-';
                    if(!canWin(t)){
                        mp[s] = true;
                        return true;
                    }
                    //s[i-1] = s[i] = '+';
                }
            }
            mp[s] = false;
            return false;
        }
    };
    

Log in to reply
 

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