LeetCode 解題筆記：20. Valid Parentheses

作者：王一哲
日期：2026年10月1日


LeetCode 題目連結：20. Valid Parentheses

解題想法

簡單題。題目給一個字串 $s$，其中只有 3 種括號 ()[]{}，要檢查 $s$ 的括號是否成對。為了在讀取到右括號時，可以很方便地讀取對應的左括號格式，先將這 3 種括號對應的關係存成 Python dict 或 C++ map。開一個堆疊 $st$，用來存放待配對的左括號。用一個 for 迴圈依序讀取 $s$ 的字元 $c$，如果 $c$ 是左括號，直接推入 $st$；如果 $c$ 是右括號，檢查 $st$ 的最後一項是否為對應的左括號，如果是就移除 $st$ 的最後一項；反之，括號不成對，回傳 Fasle。如果 $s$ 所有的括號都成對，最後 $st$ 應該是空的。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.23 MB, beats 64.57%.

class Solution:
    def isValid(self, s: str) -> bool:
        bracket = {')': '(', ']': '[', '}': '{'}  # 右括號對應的左括號
        st = []  # 存放括號用的堆疊
        for c in s:  # 依序讀取字元
            if c in "([{":  # 左括號，推入 st
                st.append(c)
            else:  # 右括號
                if st and st[-1] == bracket[c]:  # st 最後一項是對應的左括號
                    st.pop()  # 移除
                else:  # st 最後一項不是對應的左括號
                    return False  # 不合法
        # 最後 st 必須是空的
        return not st

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.97 MB, beats 37.05%.

class Solution {
public:
    bool isValid(string s) {
        map<char, char> bracket = {{')', '('}, {']', '['}, {'}', '{'}};  // 右括號對應的左括號
        stack<char> st;  // 存放括號用的堆疊
        for(char c : s) {  // 依序讀取字元
            if (c == '(' || c == '[' || c == '{') {  // 左括號，推入 st
                st.push(c);
            } else {  // 右括號
                if (!st.empty() && st.top() == bracket[c]) {  // st 最後一項是對應的左括號
                    st.pop();  // 移除
                } else {  // st 最後一項不是對應的左括號
                    return false;  // 不合法
                }
            }
        }
        // 最後 st 必須是空的
        return st.empty();
    }
};