【Day30】1190.反转每对括号间的子串

1190. 反转每对括号间的子串

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

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

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

示例 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 中只有小写英文字母和括号
  • 我们确保所有括号都是成对出现的

题解:

挨个遍历, 左括号和普通字符直接入栈;遇到右括号 ,就依次出栈直到栈顶为左括号 ,出栈的这些字符按出栈顺序链接自然也就是逆序的,然后栈顶左括号出栈 把组合成的逆序串重新压入栈。

遍历完字符串 栈中从栈底到栈顶 自然也就想要的结果,如果依次出栈 要注意连接顺序,还需要一次整体反转。

代码:

class Solution {
public:
    string reverseParentheses(string s) {
        stack st;
        for (auto c : s) {
            if (c != ')') {
                st.push(c);
            } else {
                string tmp;
                while (st.top() != '(') {
                    tmp += st.top();
                    st.pop();
                }
                st.pop();
                for (auto s : tmp) {
                    st.push(s);
                }
            }
        }
        string ans;
        while (!st.empty()) {
            ans = st.top() + ans; st.pop();
        }
        return ans;
    }
};

   转载规则


《【Day30】1190.反转每对括号间的子串》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day31】461.汉明距离 【Day31】461.汉明距离
461. 汉明距离两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。 给出两个整数 x 和 y,计算它们之间的汉明距离。 注意: 0 ≤ x, y < 231. 示例: 输入: x = 1, y = 4 输出:
2021-05-27
下一篇 
【Day29】1787.使所有区间的异或结果为零 【Day29】1787.使所有区间的异或结果为零
1787. 使所有区间的异或结果为零给你一个整数数组 nums 和一个整数 k 。区间 [left, right](left <= right)的 异或结果 是对下标位于 left 和 right(包括 left 和 right )之
2021-05-25
  目录