C++ Simple Solution, DP AND Backtrace, beat 76%


  • 0

    Similar with Can I Win
    Inspired by @shallpion 's code

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

Log in to reply
 

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