您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 程式開發 >> iOS 開發綜合

ACM 括號配對問題:用堆疊判斷是否合法

編輯:iOS 開發綜合

括號配對是經典的資料結構題。給定一行只包含 [ ] ( ) 的字串,要判斷括號是否正確配對。

解題思路

最直觀的方法是使用堆疊。遇到左括號就放入堆疊,遇到右括號時檢查堆疊頂端是否為對應的左括號。若可配對就彈出,否則失敗。

邊界條件

若遍歷結束後堆疊不為空,代表還有未閉合的括號;若中途遇到右括號但堆疊為空,也代表不合法。

範例

例如 [(]) 看似有括號,但順序錯誤,因此結果為 No;(]) 也無法配對;而 ([[]()]) 能逐層閉合,結果為 Yes。

實作提醒

使用 C++ 時,可將未匹配字元放入 vector 或 stack。每次比對最後一個元素,若符合一對就移除。最後只需檢查容器是否為空。

複雜度

此方法只需掃描一次字串,時間複雜度為 O(n),空間複雜度取決於括號嵌套深度。

  1. 上一篇文章:
  2. 下一篇文章:
蘋果刷機越獄教程| IOS教程問題解答| IOS技巧綜合| IOS7技巧| IOS8教程
Copyright © IOS教程網 All Rights Reserved