題目：
20、有效的括號
給定一個只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字串 s ，判斷字串是否有效，
有效字串需滿足：
左括號必須用相同型別的右括號閉合，
左括號必須以正確的順序閉合，
示例 1：
輸入：s = “()”
輸出：true
示例 2：
輸入：s = “()[]{}”
輸出：true
示例 3：
輸入：s = “(]”
輸出：false
示例 4：
輸入：s = “([)]”
輸出：false
示例 5：
輸入：s = “{[]}”
輸出：true
提示：
1 <= s.length <= 10^4
s 僅由括號 ‘()[]{}’ 組成
題解思路：
判斷括號的有效性可以使用「堆疊」這一資料結構來解決，
我們遍歷給定的字串 s，當我們遇到一個左括號時，我們會期望在后續的遍歷中，有一個相同型別的右括號將其閉合，由于后遇到的左括號要先閉合，因此我們可以將這個左括號放入堆疊頂，
當我們遇到一個右括號時，我們需要將一個相同型別的左括號閉合，此時，我們可以取出堆疊頂的左括號并判斷它們是否是相同型別的括號，如果不是相同的型別，或者堆疊中并沒有左括號，那么字串 s 無效，回傳 False，為了快速判斷括號的型別，我們可以使用哈希表存盤每一種括號，哈希表的鍵為右括號，值為相同型別的左括號，
在遍歷結束后，如果堆疊中沒有左括號，說明我們將字串 s 中的所有左括號閉合，回傳 True，否則回傳 False，
注意到有效字串的長度一定為偶數，因此如果字串的長度為奇數，我們可以直接回傳 False，省去后續的遍歷判斷程序，
復雜度分析
時間復雜度：O(n)O(n)，其中 nn 是字串 ss 的長度，
——
空間復雜度：O(n+∣Σ∣)，其中 Σ 表示字符集，本題中字串只包含 66 種括號，∣Σ∣=6，堆疊中的字符數量為 O(n)，而哈希表使用的空間為 O(∣Σ∣)，相加即可得到總空間復雜度，
題解python代碼：
class Solution:
def isValid(self, s: str) -> bool:
if len(s) % 2 == 1:
return False
pairs = {
")": "(",
"]": "[",
"}": "{",
}
stack = list()
for ch in s:
if ch in pairs:
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
else:
stack.append(ch)
return not stack
作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/valid-parentheses/solution/you-xiao-de-gua-hao-by-leetcode-solution/
來源：力扣（LeetCode）https://leetcode-cn.com/problems/valid-parentheses/
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/264112.html
標籤：python
上一篇：設計模式之單一職責原則