20. Valid Parentheses

📘 題目敘述

給定一個只包含字元 '('、')'、'{'、'}'、'['、']' 的字串 s，請判斷該字串是否為有效的括號字串。

有效的括號字串必須符合以下條件：

每一個左括號都必須被相同類型的右括號關閉
括號必須以正確的順序關閉

條件限制

1 ≤ s.length ≤ 10^4
s 僅由上述六種括號字元組成

🧠 解題思路

我在想這題時，重點不是「比對字元」，而是思考一件事：

右括號出現時，它應該要對應到「最近還沒被關掉的左括號」

這個「最近」的概念，讓我直接聯想到 Stack（堆疊）。

因此我的想法是：

左括號出現時，先記下來，等之後來配對
右括號出現時，必須和「最後出現、但尚未配對的左括號」做比對
只要有一次配對錯誤，整個字串就不合法

為什麼要用 Stack

Stack 的特性是 後進先出（LIFO），正好符合括號的配對邏輯：

最後出現的左括號，必須最先被關閉
巢狀結構天然就是 Stack 的使用情境

所有變數

brackets：一個 stack，用來存尚未被配對的左括號
n：字串 s 的長度
t：stack 最上層的左括號，用來和目前的右括號比對

🪜 主要流程步驟

整體流程

我從左到右掃描整個字串 s，每一個字元只會做一件很明確的事情。

情況一：遇到左括號

當目前字元是：

'('
'['
'{'

代表這是一個「尚未配對的左括號」。

我的做法是：

直接把它推進 stack 中
等之後遇到對應的右括號再處理

情況二：遇到右括號

當目前字元是右括號時，需要進行配對檢查。

步驟一：檢查 stack 是否為空

如果 stack 是空的，代表：
- 沒有任何左括號可以配對
- 出現「多出來的右括號」
這種情況直接回傳 false

步驟二：檢查括號類型是否相符

取出 stack 最上層的左括號 t
根據目前的右括號種類，檢查是否配對正確：
')' 必須對應 '('
']' 必須對應 '['
'}' 必須對應 '{'
只要有一種不相符，就代表括號順序或類型錯誤，直接回傳 false

步驟三：配對成功，移除左括號

如果種類正確，表示成功配對
將 stack 最上層的左括號移除（pop）

迴圈結束後的檢查

如果 stack 是空的：
- 代表所有左括號都成功被配對
- 回傳 true
如果 stack 仍然有元素：
- 代表還有左括號沒有被關閉
- 回傳 false

整體邏輯總結

這題的核心邏輯可以濃縮成三句話：

左括號先記起來
右括號一定要對到「最近的左括號」
最後不能留下任何沒配對的左括號

只要這三件事同時成立，字串就是合法的。

💻 程式碼實作

class Solution {
public:
    bool isValid(string s) {
        stack<char> brackets;
        int n = s.size();
        for (int i = 0; i < n; i++) {
            if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
                brackets.push(s[i]);
            } else {
                if (brackets.empty()) {
                    return false;
                }
                char t = brackets.top();
                if (s[i] == ')' && t != '(') {
                    return false;
                }
                if (s[i] == ']' && t != '[') {
                    return false;
                }
                if (s[i] == '}' && t != '{') {
                    return false;
                }
                brackets.pop();
            }
        }
        return brackets.empty();
    }
};

🔗 題目連結

https://leetcode.com/problems/valid-parentheses/