20. Valid Parentheses

題目 / Problem

中文： 給定一個字串 s，裡面只包含這六種字元：(、)、{、}、[、]。請判斷這個字串是否「有效」。有效的條件是：

1. 每個左括號都必須被「同類型」的右括號關閉。
2. 左括號必須以「正確的順序」關閉（先開的後關，後開的先關）。
3. 每個右括號都必須有一個同類型的左括號與它對應。

English: Given a string s containing only the six characters (, ), {, }, [, ], determine whether it is valid. A string is valid when:

1. Every open bracket is closed by a bracket of the same type.
2. Brackets are closed in the correct order (the most recently opened bracket must be the first one closed).
3. Every closing bracket has a matching opening bracket of the same type.

Constraints / 限制： - 1 <= s.length <= 10^4 - s 只由 ()[]{} 這六種字元組成 / s consists only of the characters ()[]{}.

Worked example / 範例： - Input: s = "([)]" → Output: false 原因：) 想關閉 [，但類型不符（[ 必須由 ] 關閉），所以無效。 Reason: the ) tries to close [, but the types don't match (a [ must be closed by ]), so it's invalid.

名詞解釋 / Glossary

• 堆疊 / Stack：一種「後進先出」(LIFO, Last-In-First-Out) 的資料結構，像一疊盤子：你只能在最上面放盤子 (push)，也只能從最上面拿盤子 (pop)。最後放進去的，會最先被拿出來。A LIFO container where you only add (push) and remove (pop) at the top; the last item pushed is the first popped.

• push（入堆/壓入）：把一個元素放到堆疊最上面。To place an element on top of the stack.

• pop（出堆/彈出）：把堆疊最上面的元素拿走（並通常回傳它）。To remove (and usually return) the top element of the stack.

• top / peek（看頂端）：查看堆疊最上面的元素，但不把它拿走。Look at the top element without removing it.

• 配對 / Matching pair：( 配 )、[ 配 ]、{ 配 }。每個左括號都有唯一對應的右括號。Each open bracket has exactly one corresponding close bracket.

• 雜湊表 / Hash map (unordered_map)：一種能用「鍵」(key) 快速查「值」(value) 的表格，平均查詢時間是 O(1)。這裡用它把每個右括號對應到它的左括號。A table that maps keys to values with O(1) average lookup; here it maps each close bracket to its matching open bracket.

思路

中文： 最直覺（暴力）的想法是反覆掃描字串，每次找到一對相鄰且互相匹配的括號（例如 () 或 []）就把它刪掉，然後重新掃描，直到無法再刪。如果最後字串變空就有效，否則無效。這個方法是對的，但每次刪除後都要重新掃描，最壞情況下會做 O(n²) 的工作，對長度 10⁴ 的字串太慢，而且不斷修改字串也很麻煩。關鍵的觀察是：當我們遇到一個右括號時，唯一可能跟它配對的，一定是「最近一個還沒被關閉的左括號」。這正是「後進先出」——最後開的要最先關。能完美表達這個規則的資料結構就是堆疊。於是演算法變成：從左到右掃描字串，遇到左括號就 push 進堆疊；遇到右括號就看堆疊頂端的左括號是不是它的配對——如果堆疊是空的（沒有左括號可配）或頂端類型不符，立刻判定無效；如果相符就 pop 掉，表示這一對成功消掉了。整個字串掃完後，堆疊必須是空的（所有左括號都被關閉了），才算有效。這裡有兩個重要的不變量(invariant)：堆疊裡永遠只存放「尚未被關閉的左括號」，而且它們由底到頂正好是從外層到內層的開啟順序。

English: The brute-force idea is to repeatedly scan the string, delete any adjacent matching pair like () or [], and rescan until nothing more can be removed; if the string ends up empty it's valid. That works but rescanning after every deletion costs O(n²), too slow for length 10⁴, and mutating the string is awkward. The key insight: when you hit a closing bracket, the only thing it could possibly match is the most recently opened, not-yet-closed bracket. That "last opened, first closed" rule is the definition of a stack (LIFO). So the algorithm becomes: scan left to right; push every opening bracket onto the stack; for every closing bracket, check the top of the stack — if the stack is empty (nothing to match) or the top isn't the corresponding opener, the string is invalid immediately; if it matches, pop it (that pair is cancelled). After scanning the whole string, the stack must be empty (every opener got closed) for the string to be valid. Two invariants hold throughout: the stack contains exactly the openers still waiting to be closed, and from bottom to top they are in outer-to-inner opening order.

逐步走查 / Walkthrough

我們用範例 s = "()[]{}"（預期輸出 true）走一遍。堆疊一開始是空的 []。 We trace s = "()[]{}" (expected true). The stack starts empty [].

掃描結束，堆疊是空的 → 回傳 true。 Scan finished, stack is empty → return true.

對照一個失敗的例子 "([)]"：push (、push [，遇到 ) 時頂端是 [（不是 (），類型不符 → 立刻回傳 false。 Compare the failing case "([)]": push (, push [; at ) the top is [ (not (), mismatch → return false immediately.

Solution — C

// 演算法：用堆疊。遇到左括號就壓入，遇到右括號就檢查堆疊頂端是否為對應的左括號；
//        相符則彈出，否則無效。掃完後堆疊為空才有效。
// Algorithm: use a stack. Push openers; for each closer check the top is its matching
//            opener — pop if so, else invalid. Valid only if the stack is empty at the end.

#include <stdbool.h>   // 提供 bool / true / false 型別 / provides the bool, true, false types
#include <stdlib.h>    // 提供 malloc 與 free / provides malloc and free
#include <string.h>    // 提供 strlen / provides strlen

bool isValid(char* s) {
    int n = strlen(s);                  // 字串長度 / length of the string

    // 堆疊最多裝 n 個左括號，所以配置 n 個 char 的空間。
    // The stack holds at most n openers, so allocate space for n chars.
    // malloc 向系統要一塊記憶體，回傳指向它的指標 / malloc requests memory and returns a pointer to it.
    char* stack = (char*)malloc(n * sizeof(char));
    int top = 0;                        // top 是「下一個寫入位置」，也等於目前堆疊大小 / top = next write slot = current stack size

    for (int i = 0; i < n; i++) {       // 從左到右掃描每個字元 / scan every character left to right
        char c = s[i];                  // 取出目前字元（s[i] 是陣列索引）/ current char (s[i] is array indexing)

        if (c == '(' || c == '[' || c == '{') {
            // 是左括號：壓入堆疊。stack[top] = c 寫入，然後 top 往上加一。
            // It's an opener: push it. Write at stack[top], then advance top by one.
            stack[top] = c;
            top++;
        } else {
            // 是右括號。先檢查堆疊是不是空的：top == 0 表示沒有左括號可配對。
            // It's a closer. First check if the stack is empty: top == 0 means no opener to match.
            if (top == 0) {
                free(stack);            // 釋放記憶體，避免洩漏 / free the memory to avoid a leak
                return false;           // 沒有對應的左括號 → 無效 / no matching opener → invalid
            }

            char openTop = stack[top - 1];  // 看堆疊頂端的左括號（不先彈出）/ peek the top opener (top-1 is the last written)

            // 檢查頂端的左括號是否與目前右括號配對；不配對就無效。
            // Check whether the top opener matches the current closer; if not, invalid.
            if ((c == ')' && openTop != '(') ||
                (c == ']' && openTop != '[') ||
                (c == '}' && openTop != '{')) {
                free(stack);            // 同樣要先釋放再回傳 / free before returning
                return false;           // 類型不符 → 無效 / type mismatch → invalid
            }

            top--;                      // 配對成功：彈出頂端（把 top 減一即可）/ matched: pop by decrementing top
        }
    }

    // 掃完所有字元。若堆疊為空 (top == 0)，代表每個左括號都被關閉了 → 有效。
    // All characters scanned. If the stack is empty (top == 0), every opener was closed → valid.
    bool result = (top == 0);
    free(stack);                        // 釋放配置的記憶體 / release the allocated memory
    return result;
}

Solution — C++

// 演算法：與 C 版相同，用堆疊。左括號壓入，右括號檢查頂端是否配對。
//        這裡用 unordered_map 把每個右括號對應到它的左括號，讓比對更乾淨。
// Algorithm: same stack idea. We use an unordered_map to map each closer to its opener,
//            which makes the matching check clean and uniform.

#include <string>
#include <stack>            // std::stack 容器 / the std::stack container
#include <unordered_map>    // std::unordered_map 雜湊表 / the hash-map container

class Solution {
public:
    bool isValid(std::string s) {
        // 雜湊表：鍵是右括號，值是對應的左括號，平均 O(1) 查詢。
        // Hash map: key = closer, value = matching opener; average O(1) lookup.
        std::unordered_map<char, char> match = {
            {')', '('},
            {']', '['},
            {'}', '{'},
        };

        std::stack<char> st;            // 存放尚未關閉的左括號 / holds the openers not yet closed

        // 範圍式 for 迴圈：依序取出 s 的每個字元；c 是字元的複本。
        // Range-for loop: iterate over each char of s; c is a copy of the character.
        for (char c : s) {
            // match.count(c) 回傳 c 是否為某個右括號的鍵（0 或 1）。
            // match.count(c) tells us whether c is a closer (a key in the map): 0 or 1.
            if (match.count(c) == 0) {
                // 不是右括號 → 是左括號 → 壓入堆疊。
                // Not a closer → it's an opener → push it.
                st.push(c);
            } else {
                // 是右括號。若堆疊為空，沒有左括號可配對 → 無效。
                // It's a closer. If the stack is empty, there's no opener to match → invalid.
                // 若頂端 st.top() 不等於這個右括號需要的左括號 match[c] → 無效。
                // If the top isn't the opener this closer needs (match[c]) → invalid.
                if (st.empty() || st.top() != match[c]) {
                    return false;
                }
                st.pop();               // 配對成功：彈出頂端 / matched: pop the top
            }
        }

        // 全部掃完後，堆疊必須為空，代表每個左括號都被正確關閉了。
        // After scanning, the stack must be empty: every opener was properly closed.
        return st.empty();
    }
};

複雜度 / Complexity

• Time: O(n) — n 是字串長度。我們只從左到右掃描一次，每個字元做的 push、pop、查表（C++ 的 unordered_map 平均 O(1)）都是常數時間，所以總時間與 n 成正比。/ n is the string length. We make a single left-to-right pass, and each character does constant-time work (push/pop, and an average-O(1) map lookup in C++), so total time is proportional to n.

• Space: O(n) — 最壞情況是字串全是左括號，例如 "((((("，所有字元都被壓進堆疊，堆疊大小達到 n。/ In the worst case (all openers, e.g. "((((("), every character is pushed, so the stack grows to size n.

Pitfalls & Edge Cases

• 空堆疊時遇到右括號 / Closer when the stack is empty：例如 ")(" 或 "]"。如果不先檢查 top == 0（C）或 st.empty()（C++）就去讀頂端，會讀到不存在的元素（C 是越界、C++ 是未定義行為）。我們的程式在彈出/查看前一定先檢查，所以安全。/ For inputs like ")(", peeking the top without first checking emptiness reads invalid memory. Both solutions check first.

• 類型配錯 / Wrong-type match：例如 "(]"。光看「有左也有右」不夠，必須確認類型相符。我們明確比對 (↔)、[↔]、{↔}，所以 "(]" 會被正確判為 false。/ Having both an opener and a closer isn't enough; the types must agree. We compare exact pairs, so "(]" returns false.

• 掃完忘了檢查堆疊是否為空 / Forgetting the final empty check：例如 "((("。掃描過程不會出錯，但結束時堆疊還有東西，代表有左括號沒被關閉。一定要回傳 top == 0 / st.empty()，否則會誤判為有效。/ For "(((" nothing fails mid-scan, but leftover openers mean it's invalid — the final emptiness check catches this.

• 記憶體洩漏（僅 C）/ Memory leak (C only)：C 版用 malloc 配置堆疊，每一條 return 路徑都必須先 free，否則重複呼叫會累積洩漏。C++ 的 std::stack 會自動釋放，不需手動管理。/ Every return path in C frees the buffer; C++'s std::stack cleans up automatically.

• 奇數長度必為 false（小優化）/ Odd length is always false (minor optimization)：括號必須成對，所以長度為奇數時不可能有效。可在開頭加 if (n % 2 != 0) return false; 提早結束，但即使不加，演算法也會自然得到正確結果。/ Brackets come in pairs, so an odd-length string can't be valid; an early n % 2 check is optional since the algorithm is already correct without it.