[C++Rust]No.1190 反转每对括号间的子串

原帖地址：http://blog.leanote.com/post/dawnmagnet/lc1190

题目

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

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

 

示例 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<int> stk;unordered_map<int, int> 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()}
}