Concise one pass DP solution without stack


  • 4
    Z

    left: remaining left parentheses that haven't been paired.
    DP[i + 1]: longest paired parentheses ended at index i. (i from 0 to size - 1)

    Once we met a ')' and have unpaired '(', increase the length by 2 based on the previous DP value. The trick is that the newly generated length may not be the final DP value.

    For the following example : '(()())', note that DP index start from 1, not 0.

    Suppose we just met the second ')', DP[5] = DP[4] + 2 = 0 + 2 = 2.
    Now we should go back to the first ')' to check if there are previously matched string. If yes, add them up.
    Thus, DP[5] += DP[5 - DP[5]]

    class Solution {
    public:
        int longestValidParentheses(string s) {
            int size = (int)s.size();
            vector<int> DP(size + 1, 0);
            int left = 0, longest = 0;
            for(int i = 0; i < size; ++i){
                if(s[i] == '('){
                    left++;
                }else if(s[i] == ')' && left > 0){
                    DP[i + 1] = DP[i] + 2;
                    DP[i + 1] += DP[i + 1 - DP[i + 1]];
                    left--;
                }
                longest = max(longest, DP[i + 1]);
            }
            return longest;
        }
    };
    

  • 0
    E

    Thanks for sharing your code!
    I rewrote your code in C++ and it passed all the test cases. The issue is that I think there is no need for the DP array to be indexed from 1, so I simply start DP process from index 0 and everything seems right.
    I think it is easier to understand your code by making the index of DP array equal to the S array, is there anything wrong with my code? Please feel free to give your comment, thanks in advance!

    class Solution {
    public:
        int longestValidParentheses(string s) 
        {
            vector<int> result(s.size(), 0);
            int left = 0, maxLength = 0;
            
            for(int i = 0; i != s.size(); i++)
            {
                if(s[i] == '(')
                    left++;
                else if(left)
                {
                    left--;
                    result[i] = result[i - 1] + 2;
                    result[i] += result[i - result[i]];
                    maxLength = max(maxLength, result[i]);
                }
            }
            return maxLength;
        }
    };
    

Log in to reply
 

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