給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷字符串是否有效。

有效字符串需滿足：

左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
注意空字符串可被認為是有效字符串。

示例 1:

輸入: "()"
輸出: true

示例 2:

輸入: "()[]{}"
輸出: true

示例 3:

輸入: "(]"
輸出: false

示例 4:

輸入: "([)]"
輸出: false

示例 5:

輸入: "{[]}"
輸出: true

思路

棧先入后出特點恰好與本題括號排序特點一致，即若遇到左括號入棧，遇到右括號時將對應棧頂左括號出棧，則遍歷完所有括號后 stack 仍然為空；
建立哈希表 dic 構建左右括號對應關系：key左括號，value右括號；建立棧 stack，遍歷字符串 s 并按照算法流程一一判斷。
如果 c 是左括號，則入棧 push；
否則通過哈希表判斷括號對應關系，若 stack 棧頂出棧括號 stack.pop() 與當前遍歷括號 c 不對應，則提前返回 false
解決邊界問題：
棧 stack 為空： 此時 stack.pop() 操作會報錯；
因此，我們采用一個取巧方法，給 stack 賦初值 ? ，并在哈希表 dic 中建立 key: '?'，value:'?′ 的對應關系予以配合。此時當 stack 為空且 c 為右括號時，可以正常提前返回 false；
字符串 s 以左括號結尾： 此情況下可以正常遍歷完整個 s，但 stack 中遺留未出棧的左括號；
因此，最后需返回 len(stack) == 1，以判斷是否是有效的括號組合。

python3解法1

class Solution:
    def isValid(self, s: str) -> bool:
        # 為什么要存儲"?":"?"，如果遇到右括號的時候，在執(zhí)行dic[stack.pop()]的時候不會報錯
        dic = {"(":")","[":"]","{":"}","?":"?"}
        # 為什么stack不能是空的，如果為空，當遇到右括號的時候，stack.pop會出錯
        stack = ["?"]
        for c in s:
            if c in dic:
                stack.append(c)
            elif dic[stack.pop()] != c:
                return False
        return len(stack) == 1

python3解法2

def isValid2(s):
    if len(s) == 0 or len(s) % 2 != 0: return False
    # 創(chuàng)建一個字典，存儲括號的對應關系
    char_map = {"(": ")", "{": "}", "[": "]"}
    # 創(chuàng)建一個棧，遇到左括號就入棧，右括號就出棧
    stack = []
    for c in s:
        if c in char_map:
            # 將左括號入棧
            stack.append(c)
        else:
            # 當前字符是右括號，則將棧頂元素出棧，找到對應右括號，判斷是否與當前括號一致
            if not stack or char_map[stack.pop()] != c:
                return False
    # 字符串遍歷結束之后，棧不為空，則說明還有左括號在棧內
    if len(stack) != 0:
        return False
    return True

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/valid-parentheses