[Leetcode] Valid Parentheses 驗證有效括號對

zhkai 發布于2019-08-14 16:11 / 1742人閱讀

摘要：如棧中是，來一個變成，再來一個，變成。注意棧在或者操作之前要驗證非空，否則會拋出。代碼最后要判斷棧的大小，如果循環結束后棧內還有元素，說明也是無效的代碼

Valid Parentheses

Given a string containing just the characters "(", ")", "{", "}", "[" and "]", determine if the input string is valid.The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

棧法 復雜度

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

思路

棧最典型的應用就是驗證配對情況，作為有效的括號，有一個右括號就必定有一個左括號在前面，所以我們可以將左括號都push進棧中，遇到右括號的時候再pop來消掉。這里不用擔心連續不同種類左括號的問題，因為有效的括號對最終還是會有緊鄰的括號對。如棧中是({[，來一個]變成({，再來一個}，變成(。

注意

棧在peek或者pop操作之前要驗證非空，否則會拋出StackEmptyException。

代碼最后要判斷棧的大小，如果循環結束后棧內還有元素，說明也是無效的

代碼

public class Solution {
    public boolean isValid(String s) {
        Map map = new HashMap();
        map.put("(",")");
        map.put("[","]");
        map.put("{","}");
        Stack stk = new Stack();
        for(int i = 0; i < s.length(); i++){
            Character c = s.charAt(i);
            switch(c){
                case "(": case "[": case "{":
                    stk.push(c);
                    break;
                case ")": case "]": case "}":
                    if(stk.isEmpty() || c != map.get(stk.pop())){
                        return false;
                    }
            }
        }
        return stk.isEmpty();
    }
}

2018/2

class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        for c in s:
            if c == "(" or c == "{" or c == "[":
                stack.append(c)
            elif not stack:
                return False
            elif c == ")" and stack.pop() != "(":
                return False
            elif c == "}" and stack.pop() != "{":
                return False
            elif c == "]" and stack.pop() != "[":
                return False
        return not stack

云服務器 GPU云服務器有效性驗證 Parentheses 無法驗證對路徑無法驗證對路徑的訪問

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

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

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

摘要：假設是從下標開始到字符串結尾最長括號對長度，是字符串下標為的括號。如果所有符號都是，說明是有效的。 Longest Valid Parentheses Given a string containing just the characters ( and ), find the length of the longest valid (well-formed) parentheses...

everfight 2019-08-14 16:11 評論0 收藏0
LeetCode 20：有效的括號 Valid Parentheses

摘要：給定一個只包括，，，，，的字符串，判斷字符串是否有效。有效字符串需滿足左括號必須用相同類型的右括號閉合。注意空字符串可被認為是有效字符串。給定一個只包括 (，)，{，}，[，] 的字符串，判斷字符串是否有效。 Given a string containing just the characters (, ), {, }, [ and ], determine if the inpu...

TesterHome 2019-08-19 10:17 評論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
leetcode32 Longest Valid Parentheses 最長括號組的長度

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

happyhuangjinjin 2019-08-14 18:13 評論0 收藏0
【LeetCode Easy】020 Valid Parentheses

摘要：三種括號匹配問題，判斷參數字符串是否滿足匹配要求如空串為括號匹配問題是棧的典型應用，遇到左括號，入棧，遇到右括號，看棧頂是否是相應的左括號，若不是，則時間復雜度代碼如下思想是一樣的，不過沒有用棧這個數據結構，而是用了一個定長數組，對于參數的 Easy 020 Valid Parentheses Description: () [] {}三種括號匹配問題，判斷參數字符串是否滿足匹配要求如...

Yangyang 2019-08-16 17:09 評論0 收藏0