---
# System prepended metadata

title: LeetCode 1190. Reverse Substrings Between Each Pair of Parentheses
tags: [Leetcode]

---

# LeetCode 1190. Reverse Substrings Between Each Pair of Parentheses
[LeetCode 1190. Reverse Substrings Between Each Pair of Parentheses]([leetcode_url](https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/description/))(<font color=#FFB800>Medium</font> 69.0%)
<!-- 
(<font color=#00AF9B>Easy</font> 53.8%) 
(<font color=#FFB800>Medium</font> 39.6%)
(<font color=#FF375F>Hard</font>)
 -->
    
- 限制 :

    <ul>
    <li><code>1 <= s.length <= 2000</code></li>
    <li><code>s only contains lower case English characters and parentheses.</code></li>
    <li><code>It is guaranteed that all parentheses are balanced.</code></li>
    </ul>

- Solution
    1. 這題說實話我真的搞了蠻久的，在 string、 vector 的運算完全忘記的情況下，很難寫出來
    2. 在運算的部分，要有點像是四則運算當中的方式去寫他，用 stack 的方式去做才會比較簡單。也就是我在右括號的地方翻轉，這樣想會比較方便。
    3. 用遞迴的方式也可以，只是寫起來就會比較冗餘。
    4. 這題真的要想一下，但蠻好玩的。
    - 時間複雜度: $O(N)$
    - 空間複雜度: $O(N)$

- 程式碼
    ```c++=
    class Solution {
    public:
        string reverseParentheses(string s) {
            vector<string> stk;
            string current_string = "";

            for (auto chr : s) {
                switch (chr) {
                case '(':
                    stk.push_back(current_string);
                    current_string = "";
                    break;
                case ')':
                    reverse(current_string.begin(), current_string.end());
                    if (stk.size() > 0) {
                        current_string = stk.back() + current_string;
                        stk.pop_back();
                    }
                    break;
                default:
                    current_string += chr;
                    break;
                }
            }

            return current_string;
        }
    };
    ```
</details>