Easy to understand, mutual recursion with memoization (C++, 169ms)


  • 0
    S
    // Memoization tables
    unordered_map<string, bool> myCache, friendCache;
    
    // Reusing Flip Game I solution
    vector<string> generatePossibleNextMoves(const string& s)
    {
        vector<string> result;
        if (s.empty()) return result;
        
        for (auto i = 0; i < s.size() - 1; i++)
        {
            if (s[i] == '+' && s[i+1] == '+')
            {
                string newS = s;
                newS[i] = '-';
                newS[i+1] = '-';
                result.emplace_back(newS);
            }
        }
        
        return result;
    }
    
    // returns true when any of the possible moves returns true
    bool myMove(const vector<string>&& moves)
    {
        for (const auto& m : moves)
        {
            if (myCache.count(m) > 0)
                if (myCache[m]) return true;
                else continue;
    
            if (friendMove(generatePossibleNextMoves(m)))
            {
                myCache[m] = true;
                return true;
            }
        }
        return false;
    }
    
    // returns true when all possible moves returns true
    bool friendMove(const vector<string>&& moves)
    {
        for (const auto& m : moves)
        {
            if (friendCache.count(m) > 0)
                if (friendCache[m]) continue;
                else return false;
            
            if (!myMove(generatePossibleNextMoves(m)))
            {
                friendCache[m] = false;
                return false;   
            }
        }
        return true;
    }
    
    // Entry point
    bool canWin(string s)
    {
            return myMove(generatePossibleNextMoves(s));
    }
    

Log in to reply
 

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