[Leetcode] Valid Parentheses 驗(yàn)證有效括號對

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

摘要：如棧中是，來一個(gè)變成，再來一個(gè)，變成。注意棧在或者操作之前要驗(yàn)證非空，否則會(huì)拋出。代碼最后要判斷棧的大小，如果循環(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ù)雜度

時(shí)間 O(N) 空間 O(N)

思路

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

注意

棧在peek或者pop操作之前要驗(yàn)證非空，否則會(huì)拋出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