Very direct DP solution, clean and efficient besides it's beautifully explained


  • 3

    Searching for the equation is always the key in DP problem, in this problem we are about to suppose the longest till the current,

    maxSub[len] = {0};

    always stick this in mind before reading the following code.

    Once we encounter a closing bracket ) then we check its previous longest valid parentheses and try to find its corresponding open bracket (

    int t = i-maxSub[i-1]

    to check whether there is a corresponding open bracket (

    if(t>0 && s[t-1] == '(')

    if there is, then we should retrieve the longest for the current closing bracket )

    maxSub[i] = (t>1? maxSub[t-2] : 0)+maxSub[i-1]+2;

    at last, we update the global longest and there.

    We're done the job easily and beautifully.

    Enjoy your day...

    class Solution {
    public:
        int longestValidParentheses(string s) 
        {
            int len = s.length(), longest = 0;
            if(!len) return 0;
            int maxSub[len] = {0};
            for(int i = 0; i < len; ++i)
            {
                if(s[i] == ')')
                {
                    int t = i-maxSub[i-1];
                    if(t>0 && s[t-1] == '(') maxSub[i] = (t>1? maxSub[t-2] : 0)+maxSub[i-1]+2;
                    longest = max(longest, maxSub[i]);
                }
            }
            return longest;
        }
    };
    

  • 0
    D

    int t = i - maxSub[i-1]
    will cause maxSub[-1] if i == 0 and you can start from i = 1.


Log in to reply
 

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