移除无效括号的最小移除高效方法

記得有次參加編程比賽，遇到一道題目讓我卡了好久：給定一個字串，裡面夾雜著括號，像是 \這裡面，多出來的右括號和左括號讓序列亂掉。我們要移除最少的符號，讓剩下字串每個左括號都對應到右括號。傳統做法可能用遞迴窮舉，但資料量大時會爆掉，時間複雜度飆到指數級，根本不可行。

高效解法是用廣度優先搜索（BFS），這招超妙。BFS 從原始字串開始，一層層移除一個括號，檢查新字串是否有效。如果有效，就停下來；無效的話，繼續生成下一層。因為 BFS 優先處理移除次數少的狀態，所以最早找到的有效序列，移除數一定最小。實際寫碼時，我會用隊列儲存狀態，搭配雜湊表避免重複計算，這樣時間複雜度降到 O(n^2)，n 是字串長度，應付上千字元都沒問題。

細節上，得注意優化。比如先掃一遍字串，統計左括號和右括號的數量差，快速判斷潛在無效位置。實作時，我常加個小技巧：只移除可能造成無效的括號類型，避免盲目嘗試。舉個實例，輸入 \()())()\，BFS 第一層移除一個右括號後，得到 \()()()\，馬上有效，移除數為 1。這比 DFS 那種深度亂挖快多了，尤其當無效點多時，BFS 不會陷在死胡同。

學到這方法後，我在工作專案中套用過幾次，處理使用者輸入的公式檢查，速度提升好幾倍。關鍵是多練習，理解 BFS 的層次思維，別一開始就想複雜。演算法就是這樣，找到對的工具，問題就變簡單。大家試試看，歡迎分享心得！