LeetCode 20：有效的括號——棧的經典應用

題目描述

給定一個只包含 '('、')'、'{'、'}'、'['、']' 的字符串，判斷括號是否有效。有效條件：左括號必須用相同類型的右括號閉合，且閉合順序正確。

示例

• "()"、"()[]{}" → true
• "(]"、"([)]" → false

解題思路：棧

1. 遍歷字符串
2. 遇到左括號 (、{、[ 入棧
3. 遇到右括號：若棧為空或棧頂不匹配 → false；否則彈出棧頂
4. 遍歷結束，棧為空 → true，否則 false

匹配規則表

C++ 實現

#include <stack>
#include <string>
using namespace std;

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for (char c : s) {
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } else {
                if (st.empty()) return false;
                char top = st.top();
                if ((c == ')' && top != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{')) return false;
                st.pop();
            }
        }
        return st.empty();
    }
};

複雜度

• 時間：O(n)
• 空間：O(n) 最壞情況全為左括號

常見錯誤

• 忽略棧為空時嘗試彈出
• 未處理字符串長度為奇數的快速判斷
• 混淆左右括號匹配關係