【LeetCode】32. 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，用栈：1.遍历字符串，当遇到'('的时候，把其索引放入堆栈，当遇到')'时候，如果栈顶是'('，则出栈操作一次，否则索引入栈

　　　2.当栈为空时候，说明字符串全体合法，返回字符串长度

　　　3.如果栈不为空，则比较栈中相邻索引的“空洞”长度，最长的空洞即为所求

 1 class Solution {
 2 public:
 3     int longestValidParentheses(string s) {
 4         int n=s.length(),i,longest=0;
 5         stack<int> st;
 6         for(i=0;i<n;i++){
 7             if('('==s[i])
 8                 st.push(i);
 9             else{
10                 if(!st.empty()){
11                     if(s[st.top()]=='(')
12                         st.pop();
13                     else
14                         st.push(i);
15                 }
16                 else{
17                     st.push(i);
18                 }
19             }
20         }
21         if(st.empty()) longest = n;
22         else{
23             int rear=n,front=0;
24             while(!st.empty()){
25                 front=st.top();
26                 st.pop();
27                 longest = max(longest,rear-1-front);
28                 rear = front;
29             }
30             longest = max(longest,front);
31         }
32         return longest;
33     }
34 };

思路2：动态规划

用longest[]记录字符串中截至每个位置时的最长合法字符串长度

如果s[i]为'('，那么longest[i]为0，因为左右以'('结尾的字符串肯定不合法，为0

如果s[i]为')'，那么分两种情况

　　　　1.当s[i-1]为'('时候， longest[i] = longest[i-2] + 2

　　　　2.当s[i-1]为')'，和s[i-longest[i-1]-1] == '('时，longest[i] = longest[i-1] + 2 + longest[i-longest[i-1]-2]；

　　　　　　longest[i-longest[i-1]-2]代表上一个以')'结尾的合法字符串

 1 class Solution {
 2 public:
 3     int longestValidParentheses(string s) {
 4         int len=s.length();
 5         if(len<=1)
 6             return 0;
 7         int curmax=0;
 8         vector<int> longest(len,0);
 9         for(int i=1;i<len;i++){
10             if(')'==s[i]){
11                 if('('==s[i-1]){
12                     longest[i]=(i-1>0?longest[i-2]+2:2);
13                     curmax=max(longest[i],curmax);
14                 }
15                 else{
16                     if(i-longest[i-1]-1>=0&&s[i-longest[i-1]-1]=='('){
17                         longest[i]=longest[i-1]+2+(i-longest[i-1]-1>0?longest[i-longest[i-1]-2]:0);
18                         curmax=max(longest[i],curmax);
19                     }
20                 }
21             }
22         }
23         return curmax;
24     }
25 };