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.

分析

无

使用栈

  1. // Longest Valid Parenthese
  2. // 使用栈，时间复杂度O(n)，空间复杂度O(n)
  3. class Solution {
  4. public:
  5.     int longestValidParentheses(const string& s) {
  6.         int max_len = 0, last = -1; // the position of the last ')'
  7.         stack<int> lefts;  // keep track of the positions of non-matching '('s
  9.         for (int i = 0; i < s.size(); ++i) {
  10.             if (s[i] =='(') {
  11.                 lefts.push(i);
  12.             } else {
  13.                 if (lefts.empty()) {
  14.                     // no matching left
  15.                     last = i;
  16.                 } else {
  17.                     // find a matching pair
  18.                     lefts.pop();
  19.                     if (lefts.empty()) {
  20.                         max_len = max(max_len, i-last);
  21.                     } else {
  22.                         max_len = max(max_len, i-lefts.top());
  23.                     }
  24.                 }
  25.             }
  26.         }
  27.         return max_len;
  28.     }
  29. };

Dynamic Programming, One Pass

  1. // Longest Valid Parenthese
  2. // 两遍扫描，时间复杂度O(n)，空间复杂度O(1)
  3. // @author 曹鹏(http://weibo.com/cpcs)
  4. class Solution {
  5. public:
  6.     int longestValidParentheses(const string& s) {
  7.         int result = 0, depth = 0, start = -1;
  8.         for (int i = 0; i < s.size(); ++i) {
  9.             if (s[i] == '(') {
  10.                 ++depth;
  11.             } else {
  12.                 --depth;
  13.                 if (depth < 0) {
  14.                     start = i;
  15.                     depth = 0;
  16.                 } else if (depth == 0) {
  17.                     result = max(result, i - start);
  18.                 }
  19.             } 
  20.         }
  22.         depth = 0;
  23.         start = s.size();
  24.         for (int i = s.size() - 1; i >= 0; --i) {
  25.             if (s[i] == ')') {
  26.                 ++depth;
  27.             } else {
  28.                 --depth;
  29.                 if (depth < 0) {
  30.                     start = i;
  31.                     depth = 0;
  32.                 } else if (depth == 0) {
  33.                     result = max(result, start - i);
  34.                 }
  35.             } 
  36.         }
  37.         return result;
  38.     }
  39. };

两遍扫描

  1. // Longest Valid Parenthese
  2. // 两遍扫描，时间复杂度O(n)，空间复杂度O(1)
  3. // @author 曹鹏(http://weibo.com/cpcs)
  4. class Solution {
  5. public:
  6.     int longestValidParentheses(const string& s) {
  7.         int result = 0, depth = 0, start = -1;
  8.         for (int i = 0; i < s.size(); ++i) {
  9.             if (s[i] == '(') {
  10.                 ++depth;
  11.             } else {
  12.                 --depth;
  13.                 if (depth < 0) {
  14.                     start = i;
  15.                     depth = 0;
  16.                 } else if (depth == 0) {
  17.                     result = max(result, i - start);
  18.                 }
  19.             } 
  20.         }
  22.         depth = 0;
  23.         start = s.size();
  24.         for (int i = s.size() - 1; i >= 0; --i) {
  25.             if (s[i] == ')') {
  26.                 ++depth;
  27.             } else {
  28.                 --depth;
  29.                 if (depth < 0) {
  30.                     start = i;
  31.                     depth = 0;
  32.                 } else if (depth == 0) {
  33.                     result = max(result, start - i);
  34.                 }
  35.             } 
  36.         }
  37.         return result;
  38.     }
  39. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/stack-and-queue/stack/longest-valid-parentheses.html