1190.反转每对括号间的子串：递归 / 指针横跳

【LetMeFly】1190.反转每对括号间的子串：递归 / 指针横跳

力扣题目链接：https://leetcode.cn/problems/reverse-substrings-between-each-pair-of-parentheses/

给出一个字符串 s（仅含有小写英文字母和括号）。

请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。

注意，您的结果中 不应 包含任何括号。

 

示例 1：

输入：s = "(abcd)"
输出："dcba"

示例 2：

输入：s = "(u(love)i)"
输出："iloveu"
解释：先反转子字符串 "love" ，然后反转整个字符串。

示例 3：

输入：s = "(ed(et(oc))el)"
输出："leetcode"
解释：先反转子字符串 "oc" ，接着反转 "etco" ，然后反转整个字符串。

 

提示：

• 1 <= s.length <= 2000
• s 中只有小写英文字母和括号
• 题目测试用例确保所有括号都是成对出现的

解题方法一：递归

写一个dfs函数遍历传入的字符串，遇到字母则直接拼接到答案中，遇到左括号则找到对应的右括号，然后递归middle = dfs(该括号中的子串)，把middle反转后拼接到答案中。直到遍历完整个字符串为止。

• 时间复杂度$O(len(s)^2)$
• 空间复杂度$O(len(s))$

AC代码

C++

/*
 * @LastEditTime: 2026-09-27 08:49:50
 */
/*
(ed(et(oc))el)
[ed          ]
[ed        te]
[ed oc     te]
[ed oc  le te]
    两栈不可
*/
class Solution {
private:
    size_t find_end(string_view s, size_t left) {
        size_t idx = left + 1;
        for (size_t layer = 1; layer; idx++) {
            if (s[idx] == '(') {
                layer++;
            } else if (s[idx] == ')') {
                layer--;
            }
        }
        return --idx;
    }

    string dfs(string_view s) {
        string ans;
        for (size_t i = 0, n = s.size(); i < n; i++) {
            if (s[i] == '(') {
                size_t end = find_end(s, i);
                string res = dfs(s.substr(i + 1, end - i - 1));
                reverse(res.begin(), res.end());
                ans += res;
                i = end;
            } else {
                ans += s[i];
            }
        }
        return ans;
    }
public:
    string reverseParentheses(const string& s) {
        return dfs(s);
    }
};

解题方法二：指针横跳

按照题目意思模拟。使用一个指针从左到右遍历字符串，遇到左括号则跳转到对应的右括号的位置向左遍历；遇到右括号则跳转到对应的左括号的位置向右遍历。遇到字母则直接拼接到答案中。

我们可以预处理得到每个括号与之配对的括号的位置。创建一个$mate$数组，$mate[i]$表示与下标为$i$的括号匹配的括号的下标。使用一个栈，遍历字符串，遇到左括号则将其下标入栈，遇到右括号则将栈顶的下标出栈，即说明二者是一对 。

• 时间复杂度$O(len(s))$
• 空间复杂度$O(len(s))$

该算法暂未规范名称，暂时归类到双指针标签下。

AC代码

C++

/*
 * @LastEditTime: 2026-09-27 09:12:03
 */
class Solution {
public:
    string reverseParentheses(const string& s) {
        int n = s.size();
        vector<int> mate(n);
        stack<int> st;
        for (int i = 0; i < n; i++) {
            if (s[i] == '(') {
                st.push(i);
            } else if (s[i] == ')') {
                int girlfriend = st.top();
                st.pop();
                mate[girlfriend] = i;
                mate[i] = girlfriend;
            }
        }

        string ans;
        ans.reserve(n);
        for (int i = 0, direction = 1; i < n; i += direction) {
            if (s[i] == '(' || s[i] == ')') {
                i = mate[i];
                direction = -direction;
            } else {
                ans += s[i];
            }
        }
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源