How to Reverse Substrings Between Each Pair of Parentheses using

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

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

推荐阅读:
写人作文新数学老师作文400字  我的寒假生活作文700字  家乡的云作文  生活因梦想而精彩作文800字  六一表演作文500字  我们,就这样毕业了(七七鱼发表了日志)  观《太行山上有感》有感作文600字  写人作文新来的语文老师作文400字  雨中送花  我选择了坚强作文 
评论列表
添加评论