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. public class Solution {
  4.     public int longestValidParentheses(String s) {
  5.         // the position of the last ')'
  6.         int maxLen = 0, last = -1;
  7.         // keep track of the positions of non-matching '('s
  8.         Stack<Integer> lefts = new Stack<>();
  10.         for (int i = 0; i < s.length(); ++i) {
  11.             if (s.charAt(i) =='(') {
  12.                 lefts.push(i);
  13.             } else {
  14.                 if (lefts.empty()) {
  15.                     // no matching left
  16.                     last = i;
  17.                 } else {
  18.                     // find a matching pair
  19.                     lefts.pop();
  20.                     if (lefts.empty()) {
  21.                         maxLen = Math.max(maxLen, i-last);
  22.                     } else {
  23.                         maxLen = Math.max(maxLen, i-lefts.peek());
  24.                     }
  25.                 }
  26.             }
  27.         }
  28.         return maxLen;
  29.     }
  30. }

Dynamic Programming, One Pass

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

两遍扫描

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

相关题目

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