How to Reverse Substrings Between Each Pair of Parentheses using

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

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) —

推荐阅读:
红枣美味营养可养生但是禁忌亦不少  不同包装的牛奶,你知道该如何选择吗  冬天吃羊肉如何去掉羊膻味及饮食禁忌  适度喝啤酒预防骨质疏松保持关节弹性  关于鸡蛋营养及其食用方法的十大误区  腊肉的风味和特点及腊肉的制作全过程  腊肉的营养价值及腊肉的食用禁忌  煲汤的诀窍及胡萝卜熟吃煮汤更营养  胡萝卜不但可以保护视力还对精子有益  节令食品年糕的营养价值与食用禁忌 
评论列表
添加评论