1-liner C++ DFS solution, no helper function (detailed explanation)


  • 0

    Key Observation:

    • Only the score difference int sd and tiebreaker bool tb matter in the game's outcome, i.e., a player wins if and only if his sd + tb > 0.

    • Player 1 can be guaranteed to win with scores a[0:N-1] if and only if Player 2 can be guaranteed to lose with remaining scores a[1:N-1] or a[0:N-2] to overcome the deficit score of a[0] or a[N-1].

    Then it is easy to define a DFS routine to check if the current player can win with remaining score index range [s,e), current score difference sd and tiebreaker tb (true/false) by adding some default variables.

    1-liner, practically :-)

        bool PredictTheWinner(vector<int>& a, int s = 0, size_t e = INT_MAX, int sd = 0, bool tb = true) {
          return s==e? sd+tb>0 : !PredictTheWinner(a, s+1, e=min(e,a.size()), -sd-a[s],   !tb) || 
                                 !PredictTheWinner(a, s,   e-1,               -sd-a[e-1], !tb);   
        }
    

    Since the array length a.size() <= 20, I didn't bother to memorize previous DFS results.


Log in to reply
 

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