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

問題描述

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

棧解法：直觀高效

遍歷字符串，遇到左括號入棧，遇到右括號檢查棧頂是否匹配：

• 匹配：彈出棧頂，繼續
• 不匹配或棧空：直接返回 false

遍歷結束後，棧為空則完全匹配。

完整代碼

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 == '[')) {
                    st.pop();
                } else {
                    return false;
                }
            }
        }
        return st.empty();
    }
};

關鍵點

• 早期終止：遇到右括號但棧空，或類型不匹配，立即返回 false
• 非括號字符處理：題目保證只含括號，否則需增加 else 分支返回 false
• 空字符串：視為有效，代碼自然處理（循環不執行，棧空返回 true）

複雜度

• 時間：O(n)，單次遍歷
• 空間：O(n)，最壞情況全是左括號

測試用例

""         -> true
"()"       -> true
"()[]{}"   -> true
"(]"       -> false
"([)]"     -> false
"{[]}"     -> true
"("        -> false
")"        -> false

擴展思考

若括號類型擴展到任意配對，可用哈希表 map<char,char> 存儲匹配關係，代碼更易維護：

unordered_map<char,char> mp = {{')','('}, {'}','{'}, {']','['}};
if (mp.count(c)) {  // 右括號
    if (st.empty() || st.top() != mp[c]) return false;
    st.pop();
} else {  // 左括號
    st.push(c);
}