本文共 3080 字，大约阅读时间需要 10 分钟。

原帖地址：

题目

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

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

 

示例 1：

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

示例 2：

输入：s = "(u(love)i)"输出："iloveu"

示例 3：

输入：s = "(ed(et(oc))el)"输出："leetcode"

示例 4：

输入：s = "a(bcdefghijkl(mno)p)q"输出："apmnolkjihgfedcbq"

 

提示：

• 0 <= s.length <= 2000
• s 中只有小写英文字母和括号
• 我们确保所有括号都是成对出现的

# 思路分析 这是一道字符串处理题，从题目中的意思可以得出，括号内的文字需要翻转。 如果我们使用的是边处理边翻转，如果遇到形式如`"(((((abcdefg)))))"`的字符串就会翻转非常多次数，复杂度达到了$O(N^2)$，其中$N$为字符串长度。 那么如果我们想要一次处理完成有没有可能呢。当然是有可能的，毕竟相当于最后的输出的答案只是原字符串的一个排列而已，我们只需要找到一个合适的遍历流程或者叫遍历顺序，就可以一次性输出答案。 我们先观察一个稍微复杂一点的示例，我们就从这里开始找规律。

示例： s = "a(b(c(d)e)f)g"答案： "afcdebg"

一般来说找规律的话三层就够了。所以我们套三个括号

我们将这个示例画的分散一点 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7OGq94QR-1621999217623)(https://leanote.com/api/file/getImage?fileId=60adb1ccab644116e5006658)] 然后用线把答案的顺序在这里连出来 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NscafoFd-1621999217625)(https://leanote.com/api/file/getImage?fileId=60adb34dab644116e500666a)] 是不是感觉有点规律了呢？ 如果我们再把括号加入到我们这个体系里面，假设遇到括号才进行跳转呢？ [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-trtmr9hh-1621999217627)(https://leanote.com/api/file/getImage?fileId=60adbab6ab644118e9006709)] 一下就清晰了（手绘太累了） 每次遇到括号的时候都会跳转到与之匹配的另一个括号处，并且方向会转变 既然是这样，我们就维护一个cur指针代表当前的位置，维护一个direc表示下一步前进的方向。 逻辑就是每次cur指向括号的时候，就跳转到与之匹配的另一个括号，并且方向相反（也就是取反） 至于怎么取得括号的另一个匹配括号，我们还是得用栈来实现括号的匹配，并且将其存到一个unordered_map中，方便在O(1)的时间获得。

C++代码

class Solution {
   public:    string reverseParentheses(string s) {
           stack
   
     stk;        unordered_map
    
      m;        int n = s.size();        for (int i = 0; i < n; ++i) {
               if (s[i] == '(') {
                   stk.push(i);            } else if (s[i] == ')') {
                   int pre = stk.top();                stk.pop();                m[i] = pre;                m[pre] = i;            }        }        int cur = 0, direc = 1;        string res;        while (cur < n) {
               if (isalpha(s[cur])) {
                   res.push_back(s[cur]);                cur += direc;            } else {
                   direc = -direc;                cur = m[cur] + direc;            }        }        return res;    }};
    
   

Rust代码

use std::collections::*;impl Solution {    pub fn reverse_parentheses(s: String) -> String {        let mut stack = vec![];        let mut m = HashMap::new();        let n = s.len();        for (i, ch) in s.chars().enumerate() {            match ch {                '(' => stack.push(i),                ')' => {                    let pre = stack.pop().unwrap();                    m.insert(i as i32, pre as i32);                    m.insert(pre as i32, i as i32);                },                _ => (),            }        }        let mut cur = 0i32;        let mut direc = 1i32;        let s_byte = s.into_bytes();        let mut res = vec![];        while (cur < n as i32) {            if (s_byte[cur as usize] > 50) {                res.push(s_byte[cur as usize]);                cur += direc;            } else {                direc = -direc;                cur = m.get(&cur).unwrap() + direc;            }        }        String::from_utf8(res).unwrap()    }}

转载地址：http://ekuci.baihongyu.com/