LeetCode 32. Longest Valid Parentheses

原題連結在這裡：https://leetcode.com/problems/longest-valid-parentheses/

題目：

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) 如果目前棧為空，則說明加上目前右括号沒有合法序列（有也是之前判斷過的）；

(2) 否則彈出棧頂元素，如果彈出後棧為空，則說明目前括号比對，我們會維護一個合法開始的起點start, 合法序列的長度即為目前元素的位置 i-start+1; 否則如果棧内仍有元素，那肯定是"(". 合法序列就會從這個"("下一位開始. 長度為目前棧頂元素的位置的下一位到目前元素的距離. i-(stk.peek()+1)+1. 因為棧頂元素後面的括号對肯定是合法的, 而 且左括号出過棧了。

Time Complexity: O(n). Space: O(n).

AC Java:

1 public class Solution {
 2     public int longestValidParentheses(String s) {
 3         if(s == null || s.length() == 0){
 4             return 0;
 5         }
 6         
 7         int res = 0;
 8         int start = 0;
 9         
10         Stack<Integer> stk = new Stack<Integer>();
11         for(int i = 0; i<s.length(); i++){
12             if(s.charAt(i) == '('){
13                 stk.push(i);
14             }else{
15                 //遇到')',但是stack是空的，說明不合法，更新 start 到 i+1
16                 if(stk.isEmpty()){
17                     start = i+1;
18                 }else{
19                     //否則彈出棧頂
20                     stk.pop();
21                     //剩下的stack為空，說明到start 到 i是合法括号對
22                     if(stk.isEmpty()){
23                         res = Math.max(res, i-start+1);
24                     }else{
25                     //身下的stack不為空，說明目前stack的棧頂 後面的括号對才是合法的
26                         res = Math.max(res, i-stk.peek());
27                     }
28                 }
29             }
30         }
31         return res;
32     }
33 }      

分别計數遇到的"(" 和")"的個數l 和 r. 先從左向右掃, l == r時跟新維護res. 當r大于l 時不合法重置為0.

在反過來從右向左掃一次.

為什麼不能一次呢. e.g. ()((). 中間出現不合法, 若最後及時r比l小, 但取出r*2. 答案就是4. 正解應該是2.

1 class Solution {
 2     public int longestValidParentheses(String s) {
 3         if(s == null || s.length() == 0){
 4             return 0;
 5         }
 6         
 7         int res = 0;
 8         int l = 0;
 9         int r = 0;
10         for(int i = 0; i<s.length(); i++){
11             if(s.charAt(i) == '('){
12                 l++;
13             }else{
14                 r++;
15             }
16             
17             if(l == r){
18                 res = Math.max(res, r*2);
19             }else if(r > l){
20                 l = 0;
21                 r = 0;
22             }
23         }
24         
25         l = 0; 
26         r = 0;
27         for(int i = s.length()-1; i>=0; i--){
28             if(s.charAt(i) == '('){
29                 l++;
30             }else{
31                 r++;
32             }
33             
34             if(l == r){
35                 res = Math.max(res, r*2);
36             }else if(l > r){
37                 l = 0;
38                 r = 0;
39             }
40         }
41         return res;
42     }
43 }