DP and stack solution in C++, both accepted as best 8ms


  • 2
    class Solution {
    public:
        //stack - 8ms;
        int longestValidParentheses(string s) 
        {
            int len = s.length(), longest = 0;
            if(!len) return 0;
            int stack[len]{0}, top = -1;
            stack[++top] = -1;
            for(int i = 0; i < len; ++i)
            {
                int t = stack[top];
                if(t!=-1 && s[i]==')' && s[t]=='(')
                    longest = max(longest, i-stack[--top]);
                else stack[++top] = i;
            }
            return longest;
        }
    
        //DP - 8ms;
    	int longestValidParentheses(string s) 
        {
            int len = s.length(), longest = 0;
            if(!len) return 0;
            int t = 0, maxSub[len]{0};
            memset(maxSub, 0, sizeof(int)*len);
            for(int i = 0; i < len; ++i)
            {
                if(i>0 && s[i] == ')')
                {
                    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;
        }
    };

  • 1
    H

    @LHearen why you can visit stack[-1] and maxSub[-1]?


  • 2

    @HongXu_1994 You are right on that point, thank you for pointing it out! My mistake here. I've updated it.

    But as for the first stack[-1] case, there is no chance for that situation since there is a condition before that indexing.


  • 0
    H

    @LHearen You are right, "++top" not "top++". My mistake.


Log in to reply
 

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