Clean c++ DP solution


  • 1

    Use a hashmap to save the result for duplicate search.
    And I changed the function parameter to pass by reference to save some time.

    public:
        bool canWin(string &s) {
            if (isWin.find(s) != isWin.end()) {
                return isWin[s];
            }
            int size = s.size();
            for (int i = 1; i < size; i++) {
                if (s[i] == s[i - 1] && s[i] == '+') {
                    s[i] = s[i - 1] = '-';
                    bool result = canWin(s);
                    isWin[s] = result;
                    s[i] = s[i - 1] = '+';
                    if (!result) {
                        return true;
                    }
                }
            }
            return isWin[s] = false;
        }
    private:
        unordered_map<string, bool> isWin;
    

  • 0
    C

    After your memorization, will the time complexity change?


  • 0

    @chaos28 in this case, for same configuration, at most to calculate once.


  • 0
    C

    So the time complexity become O(n) where n is the length of the string ?


  • 0

    @chaos28 not for this one, looks like n ^ 2, totally n possibilities, each one takes O(n) to traverse.


Log in to reply
 

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