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

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

示例 1:
輸入: "()"
輸出: true

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

示例 3:
輸入: "(]"
輸出: false

示例 4:
輸入: "([)]"
輸出: false

示例 5:
輸入: "{[]}"
輸出: true

class Solution:
    def isValid(self, s: str) -> bool:
        dic = {'{': '}',  '[': ']', '(': ')', '?': '?'}
        stack = ['?']
        for c in s:
            if c in dic: stack.append(c)
            elif dic[stack.pop()] != c: return False 
        return len(stack) == 1

算法原理
棧先入后出特點恰好與本題括號排序特點一致，即若遇到左括號入棧，遇到右括號時將對應(yīng)棧頂左括號出棧，則遍歷完所有括號后 stack 仍然為空；
建立哈希表 dic 構(gòu)建左右括號對應(yīng)關(guān)系：keykey 左括號，valuevalue 右括號；這樣查詢 22 個括號是否對應(yīng)只需 O(1)O(1) 時間復(fù)雜度；建立棧 stack，遍歷字符串 s 并按照算法流程一一判斷。

算法流程
如果 c 是左括號，則入棧 pushpush；
否則通過哈希表判斷括號對應(yīng)關(guān)系，若 stack 棧頂出棧括號 stack.pop() 與當(dāng)前遍歷括號 c 不對應(yīng)，則提前返回 falsefalse。
提前返回 falsefalse

提前返回優(yōu)點： 在迭代過程中，提前發(fā)現(xiàn)不符合的括號并且返回，提升算法效率。
解決邊界問題：
棧 stack 為空： 此時 stack.pop() 操作會報錯；因此，我們采用一個取巧方法，給 stack 賦初值 ?? ，并在哈希表 dic 中建立 key: '?'，value:'?'key: ′? ′，value: ′? ′的對應(yīng)關(guān)系予以配合。此時當(dāng) stack 為空且 c 為右括號時，可以正常提前返回false；
字符串 s 以左括號結(jié)尾： 此情況下可以正常遍歷完整個 s，但 stack 中遺留未出棧的左括號；因此，最后需返回 len(stack) == 1，以判斷是否是有效的括號組合。
復(fù)雜度分析

時間復(fù)雜度 O(N)O(N)：正確的括號組合需要遍歷 11 遍 s；
空間復(fù)雜度 O(N)O(N)：哈希表和棧使用線性的空間大小。

來源：力扣（LeetCode）