[Leetcode] Longest Valid Parentheses 最長有效括號對

everfight 發布于2019-08-14 16:11 / 2829人閱讀

摘要：假設是從下標開始到字符串結尾最長括號對長度，是字符串下標為的括號。如果所有符號都是，說明是有效的。

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.

棧法 Stack 復雜度

時間 O(N) 空間 O(N)

思路

用Stack的方法本質上和Valid Parentheses是一樣的，一個右括號能消去Stack頂上的一個左括號。不同的是，為了能夠計算括號對的長度我們還需要記錄括號們的下標。這樣在彈出一個左括號后，我們可以根據當前坐標減去棧中上一個（也就是Pop過后的Top元素）的坐標來得到該有效括號對的長度。

代碼

public class Solution {
    public int longestValidParentheses(String s) {
        Stack stk = new Stack();
        int maxLen = 0;
        for(int i = 0; i < s.length(); i++){
            //遇到左括號，將其push進棧
            if(s.charAt(i)=="("){
                stk.push(new Parenthese(i, "("));
            } else {
           //遇到右括號，分類討論
               //如果當前棧頂是左括號，則消去并計算長度
                if(!stk.isEmpty() && stk.peek().symb=="("){
                    int curLen = 0;
                    stk.pop();
                    if(stk.isEmpty()){
                        curLen = i + 1;
                    } else {
                        curLen = i - stk.peek().indx;
                    }
                    maxLen = Math.max(maxLen, curLen);
                } else {
               //如果棧頂是右括號或者是空棧，則將右括號也push進棧，它的坐標將方便之后計算長度
                    stk.push(new Parenthese(i, ")"));
                }
            }
        }
        return maxLen;
    }
    
    public class Parenthese {
        int indx;
        char symb;
        public Parenthese (int i, char s){
            this.indx = i;
            this.symb = s;
        }
    }
}

動態規劃法 Dynamic Programming 復雜度

時間 O(N) 空間 O(N)

思路

動態規劃法將大問題化為小問題，我們不一定要一下子計算出整個字符串中最長括號對，我們可以先從后向前，一點一點計算。假設d[i]是從下標i開始到字符串結尾最長括號對長度，s[i]是字符串下標為i的括號。如果s[i-1]是左括號，如果i + d[i] + 1是右括號的話，那d[i-1] = d[i] + 1。如果不是則為0。如果s[i-1]是右括號，因為不可能有右括號開頭的括號對，所以d[i-1] = 0。

代碼

public class Solution {
    public int longestValidParentheses(String s) {
        int[] dp = new int[s.length()];
        int maxLen = 0;
        for(int i = s.length()-2; i >=0; i--){
            if(s.charAt(i)=="("){
                int end = i + dp[i+1] + 1;
                if(end < s.length() && s.charAt(end)==")"){
                    dp[i] = dp[i+1] + 2;
                    if(end + 1 < s.length()){
                        dp[i] += dp[end + 1];
                    }
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }
}

后續 Follow Up

Q：能否不用額外空間求解？
A：可以，但是要提高時間復雜度。比如((()())，先遍歷一遍將所有的()替換成00，得到((0000)，再遍歷一遍，替換所有的(00...00)這種形式字符串為000...000，這里我們得到(000000，直到遍歷完無法替換更多括號為之。如果所有符號都是0，說明是有效的。這樣的時間復雜度是O(N)。

云服務器 GPU云服務器 Parentheses Longest LeetCode Valid

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66168.html

leetcode32 Longest Valid Parentheses 最長括號組的長度

摘要：題目要求原題地址一個括號序列，求出其中成對括號的最大長度思路一使用堆棧這題可以參考我的另一篇博客這篇博客講解了如何用堆棧判斷括號序列是否可以成對。我們可以將堆棧的思路延續到這里。在這里需要先遍歷一遍字符串，再遍歷一下非空的堆棧。題目要求原題地址：https://leetcode.com/problems... Given a string containing just the c...

happyhuangjinjin 2019-08-14 18:13 評論0 收藏0
[leetcode]Longest Valid Parentheses

摘要：在問題中，我們可以用來檢驗括號對，也可以通過來檢驗。遇到就加一，遇到就減一。找到一對括號就在最終結果上加。我們用來表示當前位置的最長括號。括號之間的關系有兩種，包含和相離。 Longest Valid Parentheses Given a string containing just the characters ( and ), find the length of the lon...

qujian 2019-08-14 16:53 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
[LeetCode] 32. Longest Valid Parentheses

Problem Given a string containing just the characters ( and ), find the length of the longest valid (well-formed) parentheses substring. Example 1: Input: (()Output: 2Explanation: The longest valid pa...

Flink_China 2019-08-19 11:14 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0