括號配對是經典的資料結構題。給定一行只包含 [ ] ( ) 的字串,要判斷括號是否正確配對。
最直觀的方法是使用堆疊。遇到左括號就放入堆疊,遇到右括號時檢查堆疊頂端是否為對應的左括號。若可配對就彈出,否則失敗。
若遍歷結束後堆疊不為空,代表還有未閉合的括號;若中途遇到右括號但堆疊為空,也代表不合法。
例如 [(]) 看似有括號,但順序錯誤,因此結果為 No;(]) 也無法配對;而 ([[]()]) 能逐層閉合,結果為 Yes。
使用 C++ 時,可將未匹配字元放入 vector 或 stack。每次比對最後一個元素,若符合一對就移除。最後只需檢查容器是否為空。
此方法只需掃描一次字串,時間複雜度為 O(n),空間複雜度取決於括號嵌套深度。