LeetCode 20 Valid Parentheses - 判斷括號字符串有效性

棧模擬匹配（標準解）

遍歷字符串：

• 遇左括號 ([{ 入棧。
• 遇右括號 )]}：若棧空或棧頂不匹配 → 無效；否則彈出棧頂。

遍歷結束後棧為空 → 有效，否則無效。

代碼實現 (C++ / Java / Python)

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2) return false; // 奇數長度必無效
        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 != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{')) return false;
            }
        }
        return st.empty();
    }
};

public class Solution {
    public boolean isValid(String s) {
        if (s.length() % 2 != 0) return false;
        Deque st = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') st.push(c);
            else {
                if (st.isEmpty()) return false;
                char top = st.pop();
                if ((c == ')' && top != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{')) return false;
            }
        }
        return st.isEmpty();
    }
}

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2: return False
        st = []
        pairs = {')': '(', ']': '[', '}': '{'}
        for c in s:
            if c in pairs.values():
                st.append(c)
            else:
                if not st or st.pop() != pairs[c]:
                    return False
        return not st

複雜度

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

優化技巧

• 預先判斷長度奇數直接返回 false。
• 用哈希表 pairs 統一匹配邏輯，代碼更簡潔（如 Python 版）。
• C++ 可用 string 作為棧（push_back/pop_back）避免 stack 容器適配器開銷。

總結

括號匹配是棧的教科書級應用。面試必會，關鍵點：奇數長度快速失敗、左括號入棧、右括號匹配彈出、最終棧空判斷。可延伸討論：多類型括號、帶轉義字符、流式驗證等變體。