LeetCode Valid Parentheses：棧經典應用括號匹配驗證

LeetCode 20. Valid Parentheses 解題詳解：棧模擬括號匹配

給定只含 ()[]{} 的字符串，判斷括號是否合法：左括號必須與同類型右括號按正確順序閉合。

棧算法

1. 遍歷字符：左括號 ({[ 入棧。
2. 遇到右括號 )}]：若棧空 → 非法；否則彈出棧頂，檢查類型是否匹配（()、[]、{}），不匹配 → 非法。
3. 遍歷結束：棧空 → 合法，否則非法（有未閉合左括號）。

C++ 實現

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

複雜度

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

擴展：多類型括號匹配通用模板

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

利用哈希表存儲匹配關係，代碼更簡潔、易擴展新括號類型。