An intuitive (4ms) solution, a DP solution (0ms) and an optimized clean DP solution (0ms) in C


  • 6

    A direct solution is to traverse the string and record the index of '(' until its corresponding ')' in a stack in which process we can get the longest for different sections of valid parentheses and then using a variable max to record the current longest valid parentheses we handled so far; till the end, we return the max - the longest valid parentheses in the string.

    • Time Cost O(n)
    • Space Cost O(n)

    //AC - 4ms;
    int longestValidParentheses(char* s)
    {
        int len = strlen(s);
        int *stack = (int*)malloc(sizeof(int)*len);
        int top = -1;
        stack[++top] = -1;
        int max = 0;
        for(int i = 0; i < len; i++)
        {
            int t = stack[top];
            if(t!=-1 && s[i]==')' && s[t]=='(')
            {
                if(i-stack[--top] > max)
                    max = i-stack[top];
            }
            else
                stack[++top] = i;
        }
        return max;
    }
    

    Using DP is quite simpler and easy to understand, here we can use an array maxs[] to store the longest till the current position of the string - the index of maxs[] is the same as that of the string.

    • When the current character is '(' then maxs[current]=0, quite intuitive;
    • when the current character is ')' we need to consider the previous state maxs[current-1] and s[current-1]:
    • at this time if s[current-1]=='(' we need further check the maxs[current-2] to get the longest valid parentheses;
    • if s[current-1]==')' then we need to check s[i-maxs[current-1]-1] and maxs[i-maxs[current-1]-2] to get the longest for maxs[current].

    Confused? check an example here: "()(())" if we reached the last ')', then the maxs[current-1]=2 and obviously this is not the longest for maxs[current] and to get the longest we need to check the third character which is the last character not covered by maxs[current-1] -- s[current-maxs[current-1]-1] is the character and then the maxs[current-maxs[current-1]-2] which is the first parentheses in this example.

    • Time Cost O(n)
    • Space Cost O(n)

    //AC - 0ms - DP solution;
    int longestValidParentheses2(char* s)
    {
        int len = strlen(s);
        if(len < 2) return 0;
        int max = 0;
        int *maxs = (int*)malloc(sizeof(int)*len); //record the max viable length ending with the current;
        memset(maxs, 0, sizeof(int)*len);
        for(int i = 1; i < len; i++)
        {
            if(s[i] == ')')
            {
                if(s[i-1] == '(')
                        maxs[i] = 2+ (i>1? maxs[i-2] : 0);
                else if(i-maxs[i-1] > 0 && s[i-maxs[i-1]-1] == '(')
                        maxs[i] = maxs[i-1] + (i-maxs[i-1]>1? maxs[i-maxs[i-1]-2]:0) + 2; 
                if(maxs[i] > max)
                    max = maxs[i];
            }
        }
        return max;
    }
    

    In fact, just as we have analyzed in the DP solution, we can merge the two conditions s[current-1]==')' and s[current-1]=='(' altogether when s[current]==')', because if s[current-1]=='(' then maxs[current-1] will be zero which will force the second condition to be the same with the first, so we are just repeating ourselves! Here is the further optimized DP solution removing the redundancy, which is much terse and clean!

    • Time Cost O(n)
    • Space Cost O(n)

    //AC - 0ms;
    int longestValidParentheses(char* s)
    {
        int len = strlen(s);
        int max = 0;
        int *maxs = (int*)malloc(sizeof(int)*len); //record the max viable length ending with the current;
        memset(maxs, 0, sizeof(int)*len);
        for(int i = 1; i < len; i++)
            if(s[i] == ')')
            {
                int t = i-maxs[i-1];
                if(t>0 && s[t-1] == '(') maxs[i] = maxs[i-1] + (t>1? maxs[t-2]:0) + 2; 
                if(maxs[i] > max) max = maxs[i];
            }
        return max;
    }

  • 0
    E
    This post is deleted!

  • 0
    E

    For the improved algorithm, we need a check for t >= 2 before trying to add max[t-2] to ensure the index is still in bounds. Thanks for the helpful explanation!

    Sorry for adding this in the answer first


  • 0

    That's right, there is no clear way to ensure its validity but they just past the tests, maybe some some flaws in the test cases -> it's bound to cross the boundary when the case is like this "(())". Anyway, thanks for your carefulness and kindness. And I've updated the code above.


Log in to reply
 

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