題目描述
給定一個只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判斷字符串是否有效。
有效字符串需滿足：
左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
每個右括號都有一個對應的相同類型的左括號。
思路與算法
- 棧的使用：
當我們遍歷字符串 s 中的每個字符時：- 如果遇到 左括號（‘(’, ‘{’, ‘[’），我們將其壓入棧中。
- 如果遇到 右括號（), }, ]），我們檢查棧頂的元素：
- 如果棧為空，說明沒有對應的左括號，返回 False。
- 如果棧頂元素是對應的左括號（例如，遇到 ) 時，棧頂應該是 ‘(’），則將棧頂元素彈出，繼續檢查下一個字符。
- 如果匹配不成功，立即返回 False。
- 字符串遍歷完成后：
如果棧為空，說明所有的括號都已成功匹配，返回 True。
如果棧不為空，說明還有未匹配的左括號，返回 False。
代碼
class Solution:def isValid(self, s: str) -> bool:# 初始化一個棧來存儲左括號stack = []# 初始化哈希表，存儲括號的配對關系bracket_map = {')':'(', '}':'{',']':'['}# 遍歷for char in s:# 如果是右括號if char in bracket_map:# 檢查棧頂是否匹配top_element = stack.pop() if stack else '#'if top_element != bracket_map[char]:return Falseelse:stack.append(char)return not stack使用一個哈希表 bracket_map 來存儲右括號對應的左括號映射。這樣當遇到一個右括號時，我們就可以通過查找哈希表快速獲得它對應的左括號 if top_element != bracket_map[char]:
此外，在字典中，in 運算符默認檢查的是字典的鍵，而不是值。
總結
- 在 Python 中，列表有以下幾種方法可以幫助我們模擬棧的行為：
append(x)：將元素 x 推入棧的頂部（即列表的末尾）。
pop()：移除并返回棧頂部的元素（即列表的最后一個元素）。
這兩個方法完美地支持棧的基本操作（壓棧和彈棧），因此我們可以利用列表來實現棧的功能。 - 使用棧和哈希表處理括號匹配是常見的技巧.
