LeetCode Longest Valid Parentheses: 2 Methods DP and Stack

Overview

LeetCode Longest Valid Parentheses: 1) Dynamic Programming, f(i) is the longest valid length ended at s[i]; 2) using Stack to find matched pair parentheses.

LeetCode Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Solution and Precautions: 2 Methods DP and Stack

1) Dynamic Programming: Define f(i) to be the longest length of the valid parentheses ended at s[i], and only the following two cases, dp[i] could be calculated from a recursive definition, otherwise it is zero.

  1. if s[i] is ‘)’ and s[i-1] is equal to ‘(‘, then dp[i] = dp[i-2] + 2
  2. if s[i] is ‘)’ and s[i-1] is equal to ‘)’ and s[i - dp[i-1] – 1] is equal to ‘(‘, then dp[i] =  dp[i-1] + 2 + dp[i - dp[i-1] – 2]

As long as we know all such dp[i], the maximum among them is our answer. So the following code implements this idea and is accepted by the LeetCode OJ to pass this Longest Valid Parentheses:

class Solution {
    public:
        int longestValidParentheses(string s) {
            int n = s.size();
            int len = 0;
            vector<int> dp(n, 0);

            for (int i = 1; i < n; ++i) {
                if (')' == s[i]) {
                    if ('(' == s[i-1]) {
                        dp[i] = 2;
                        if (i >= 2)
                            dp[i] += dp[i-2];
                    }
                    else {
                        int idx = i - dp[i-1] - 1;
                        if (idx >= 0 && '(' == s[idx]) {
                            dp[i] = dp[i-1] + 2;
                            if (idx > 0)
                                dp[i] += dp[idx -1];
                        }
                    }
                }
                len = max(len, dp[i]);
            }
            return len;
        }
};

2) Using Stack: This problem could be solved by linear scan as well. That is, maintain a stack, and scan the string from left to right, if it is ‘(‘, just push it (the index of this character) into the stack, if it is ‘)’, there are two cases, if the stack is NOT empty and the top is ‘(‘, then pop the stack out, get the current length of the valid sub string (current index  -  the top index in the stack after popping). Update the global maximum length if this length is larger. The second case (otherwise), we just push ‘)’ into the stack.

The key point here is that: when we encounter a ‘)’ at position B and pop out a matched ‘(‘ at position A, we know the string between S[A, B] must be a valid Parentheses. The following code implements this idea and is accepted by the LeetCode OJ to pass this Longest Valid Parentheses:

class Solution {
    public:
        int longestValidParentheses(string s) {
            int n = s.size();
            int len = 0;
            int tmp = 0;

            stack<int> stk;
            for (int i = 0; i < n; ++i) {
                if ('(' == s[i])
                    stk.push(i);
                else {
                    if (!stk.empty() && '(' == s[stk.top()]) {
                        stk.pop();
                        tmp = i - (stk.empty() ? -1 : stk.top());
                        len = max(len, tmp);
                    }
                    else {
                        stk.push(i);
                    }
                }
            }
            return len;
        }
};

Summary

LeetCode Longest Valid Parentheses: 1) Dynamic Programming, f(i) is the longest valid length ended at s[i]; 2) using Stack to find matched pair parentheses.

Written on June 5, 2013