My O(N) time C++ solutions: stack based and DP based


  • 10
    D
    • DP based solution, O(N) time O(N) space

    We can do DP: dp[i] saves the longest valid parentheses that ends at (i-1). To calculate the longest valid parentheses that ends at i (i.e. calculate dp[i+1]), we only need to consider the following cases

    1. case 1: s[i] = '(', then no valid parentheses that ends at i, so dp[i+1]=0 (i.e. do nothing)

    2. case 2 s[i]= ')' , then we have to check if this ')' can find a matched '(' just before the longest parentheses ending at i-1 (i.e. check if s[i-dp[i]-1] = '(');
      if yes, then s[i] extends the longest parentheses ending at i-1 to [i-dp[i]-1, i] and it now connects to the longest parentheses ending at i-dp[i]-2, so the DP update equation becomes dp[i+1] =dp[i]+2+dp[i-dp[i]-1]
      if no, then no valid parentheses ending at i, so dp[i+1] =0 (do nothing)

      class Solution {
      public:
      int longestValidParentheses(string s) {
      int len = s.size(), i, res=0, left;
      vector<int> dp(len+1,0);

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

      };

    3. Stack based solution, O(N) time and O(N) space
      Scan s from left to right and use a stack to save all the unmatched '(' or ')' indices. If s[i] ='(', then push i to the stack; if s[i] =')', check if it can match the last unmatched char (i.e. check if s[stk.top()]='('), if so, remove tthe top entry and update res if the current parentheses [stk.top(), i] is longer than res.

    class Solution {
    public:
        int longestValidParentheses(string s) {
            int len = s.size(), maxL=0, i;
            stack<int> stk;
            stk.push(-1);
            for(i=0; i<len;++i)
            {
                if(s[i]==')' && stk.top()>=0 && s[stk.top()]=='(')
                { // if s[i] is ')' and matches the last unmatched  char  
                    stk.pop(); // remove the last unmatched char
                    maxL = max(maxL, i-stk.top()); // update res
                }
                else stk.push(i);
            }
            return maxL;
        }
    };

Log in to reply
 

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