LeetCode 解題筆記：1190. Reverse Substrings Between Each Pair of Parentheses

作者：王一哲
日期：2026年9月27日


LeetCode 題目連結：1190. Reverse Substrings Between Each Pair of Parentheses

解題想法

中等難度題。題目給一個字串 $s$，$s$ 之中只有小寫英文字母及 (、)，括號一定成對，有巢狀結構，也就是左、右括號之間有其它的括號。要將每一對括號之間的子字串反序，回傳處理完的字串。以 (u(love)i) 為例，先處理最裡面的括號，將 love 反序後變成 evol；再處理外面的括號，原來的字串為 uevoli，反序後變成 iloveu。

這題很適合用堆疊 (stack) 處理。先建一個堆疊 $st$ 並放入空字串。用一個 for 迴圈依序讀取 $s$ 的字元 $c$，依照 $c$ 的值分為 3 種狀況：

1. 左括號，新的區段，$st$ 加入空字串。
2. 右括號，結算最後一個區段。移除 $st$ 最後一項，暫存到 $t$。$t$ 反序後接到 $st$ 最後一項。
3. 字母，$c$ 接到 st 最後一項。

答案會在 $st$ 首項。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.26 MB, beats 69.70%.

class Solution:
    def reverseParentheses(self, s: str) -> str:
        st = [""]  # 儲存每一對括號內容的堆疊，先放入空字串

        for c in s:  # 依序讀取 s 的字元 c
            if c == '(':  # 左括號
                st.append("")  # 新的區段，st 加入空字串
            elif c == ')':  # 右括號，結算最後一個區段
                t = st.pop()  # 移除 st 最後一項，暫存到 t
                st[-1] += t[::-1]  # t 反序後接到 st 最後一項
            else:  # 字母
                st[-1] += c  # 接到 st 最後一項
        return st[0]  # 答案會在 st 首項

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 11.06 MB, beats 11.72%.

class Solution {
public:
    string reverseParentheses(string s) {
        stack<string> st;  // 儲存每一對括號內容的堆疊，先放入空字串
        st.push("");
        
        for(char c : s) {  // 依序讀取 s 的字元 c
            if (c == '(') {  // 左括號
                st.push("");  // 新的區段，st 加入空字串
            } else if (c == ')') {  // 右括號，結算最後一個區段
                string t = st.top();  // st 最後一項，暫存到 t
                st.pop();  // 移除 st 最後一項
                reverse(t.begin(), t.end());  // t 反序
                st.top() += t;  // t 接到 st 最後一項
            } else {  // 字母
                st.top() += c;  // 接到 st 最後一項
            }
        }
        return st.top();  // 答案會在 st 首項
    }
};

Runtime: 3 ms, beats 46.55%. Memory: 10.88 MB, beats 13.81%.

class Solution {
public:
    string reverseParentheses(string s) {
        vector<string> st = {""};  // 儲存每一對括號內容的堆疊，先放入空字串

        for(char c : s) {  // 依序讀取 s 的字元 c
            if (c == '(') {  // 左括號
                st.push_back("");  // 新的區段，st 加入空字串
            } else if (c == ')') {  // 右括號，結算最後一個區段
                string t = st.back();  // st 最後一項，暫存到 t
                st.pop_back();  // 移除 st 最後一項
                reverse(t.begin(), t.end());  // t 反序
                st.back() += t;  // t 接到 st 最後一項
            } else {  // 字母
                st.back() += c;  // 接到 st 最後一項
            }
        }
        return st[0];  // 答案會在 st 首項
    }
};