How to Reverse Substrings Between Each Pair of Parentheses using

  • 时间:2020-09-18 17:39:21
  • 分类:网络文摘
  • 阅读:97 次

You are given a string s that consists of lower case English letters and brackets. Reverse the strings in each pair of matching parentheses, starting from the innermost one. Your result should not contain any brackets.

Example 1:
Input: s = “(abcd)”
Output: “dcba”

Example 2:
Input: s = “(u(love)i)”
Output: “iloveu”
Explanation: The substring “love” is reversed first, then the whole string is reversed.

Example 3:
Input: s = “(ed(et(oc))el)”
Output: “leetcode”
Explanation: First, we reverse the substring “oc”, then “etco”, and finally, the whole string.

Example 4:
Input: s = “a(bcdefghijkl(mno)p)q”
Output: “apmnolkjihgfedcbq”

Constraints:
0 <= s.length <= 2000
s only contains lower case English characters and parentheses.
It’s guaranteed that all parentheses are balanced.

Hints:
Find all brackets in the string.
Does the order of the reverse matter?
The order does not matter.

Using Stack to Keep Tracking the Level of Parentheses

We can use a stack to keep tracking the Parentheses. Also, we can use a variable to record the current string in the current level. If we meet open bracket, we push the current string to the stack, reseting it to “”. And we meet an close bracket, we need to reverse the current string, and add it to the top element of the stack.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string reverseParentheses(string s) {
        stack<string> st;
        string cur = "";
        for (int i = 0; i < s.size(); ++ i) {            
            if (s[i] == '(') {
                st.push(cur);
                cur = "";
            } else if (s[i] == ')') {
                std::reverse(begin(cur), end(cur));
                string s = st.top();
                st.pop();
                cur = s + cur;
            } else {
                cur += s[i];
            }
        }
        return cur;
    }
};
class Solution {
public:
    string reverseParentheses(string s) {
        stack<string> st;
        string cur = "";
        for (int i = 0; i < s.size(); ++ i) {            
            if (s[i] == '(') {
                st.push(cur);
                cur = "";
            } else if (s[i] == ')') {
                std::reverse(begin(cur), end(cur));
                string s = st.top();
                st.pop();
                cur = s + cur;
            } else {
                cur += s[i];
            }
        }
        return cur;
    }
};

The complexity is O(N) and the space complexity is also O(N). The stack implements a First In Last Out, and hence is often used in the Parentheses problems.

The std::reverse() is perfect to reverse a string, substring, or a vector.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
身体健康无虚证的人不宜食用枸杞子  食疗养生枸杞子泡水喝有4大保健功效  调味品酱油对人体健康会有什么影响  便秘患者需要注意 常吃香蕉不能通便  食疗养生:女性常吃哪些食物能保健养颜  食药总局要求加强白酒质量安全监管  食品认证乱象:有钱就给有机食品证书  食品安全法中应该设立有奖举报制度  哪些健脑食品有助于增强孩子的记忆力  食药监总局:明确乳粉企业监督检查规定 
评论列表
添加评论