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

zhkai 發(fā)布于2019-08-14 16:11 / 1786人閱讀

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

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.

棧法 復(fù)雜度

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

思路

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

注意

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

代碼最后要判斷棧的大小，如果循環(huán)結(jié)束后棧內(nèi)還有元素，說明也是無效的

代碼

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