首页 > 其他 > 详细

32. Longest Valid Parentheses

时间:2020-02-14 21:13:07      阅读:60      评论:0      收藏:0      [点我收藏+]

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

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"


 1 class Solution {
 2     
 3     public int longestValidParentheses(String s) {
 4         int n = s.length();
 5         int []f = new int[n];
 6         int []stack = new int[n];
 7         int ans = 0;
 8         int k = 0;
 9         for (int i = 0; i < n; ++i) {
10             if (s.charAt(i) == ‘(‘) {
11                 stack[k++] = i;
12             }
13             if (s.charAt(i) == ‘)‘) {
14                 if (k > 0) {
15                     f[i] = i - stack[k - 1] + 1;
16                     if (stack[k - 1] - 1 >= 0 && f[stack[k - 1] - 1] > 0)
17                         f[i] += f[stack[k - 1] - 1];
18                     k--;
19                 } else {
20                     k = 0;
21                     
22                 }
23                 
24             }
25         }
26         for (int i = 0; i < n; ++i) {
27             ans = Math.max(ans, f[i]);
28         }
29         
30         return ans;
31     }
32 }

 

32. Longest Valid Parentheses

原文:https://www.cnblogs.com/hyxsolitude/p/12309467.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!