【数据结构-合法括号字符串】【华为笔试题】力扣1190. 反转每对括号间的子串

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

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

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

示例 1：
输入：s = “(abcd)”
输出：“dcba”

示例 2：
输入：s = “(u(love)i)”
输出：“iloveu”
解释：先反转子字符串 “love” ，然后反转整个字符串。

示例 3：
输入：s = “(ed(et(oc))el)”
输出：“leetcode”
解释：先反转子字符串 “oc” ，接着反转 “etco” ，然后反转整个字符串。

提示：
1 <= s.length <= 2000
s 中只有小写英文字母和括号
题目测试用例确保所有括号都是成对出现的

栈

class Solution {
public:string reverseParentheses(string s) {stack<string> st;string str;for(char &c : s){if(c == '('){st.push(str);str = "";}else if(c == ')'){reverse(str.begin(), str.end());str = st.top() + str;st.pop();}else{str.push_back(c);}}return str;}
};

时间复杂度：O(n ^ 2 )，其中 n 为字符串的长度。栈的最大深度为 O(n)，每一层处理的时间复杂度主要为反转的时间复杂度，为 O(n)，因此总时间复杂度为 O(n ^ 2 )。
空间复杂度：O(n)，其中 n 为字符串的长度。对于任意时刻，字符串中的任意一个字符至多只被栈中的一个位置包含一次。

使用栈的方法，具体思路就是我们定义一个字符串，每当遍历到一个字母，我们就push到字符串str中，当遇到一个左括号，我们就将这个字符串push到栈中存着，令字符串重新为空。当遇到一个右括号的时候，我们令这个右括号对应的左括号之间的字符串进行反转，这时候我们栈的顶部存放着外面一层左括号到当前右括号对应左括号之间的字符串，我们令字符串为str = st.top() + str;，然后遇到新的字母，继续加入到str中。遇到右括号就让这个str继续反转，这样子就完成了从内层括号到外层括号之间字符串不断反转的过程。

---

预处理括号

class Solution {
public:string reverseParentheses(string s) {int n = s.length();vector<int> pair(n);stack<int> stk;for (int i = 0; i < n; i++) {if (s[i] == '(') {stk.push(i);} else if (s[i] == ')') {int j = stk.top();stk.pop();pair[i] = j, pair[j] = i;}}string ret;int index = 0, step = 1;while (index < n) {if (s[index] == '(' || s[index] == ')') {index = pair[index];step = -step;} else {ret.push_back(s[index]);}index += step;}return ret;}
};

时间复杂度：O(n)，其中 n 为字符串的长度。预处理出括号的对应关系的序列的时间复杂度为 O(n)，遍历字符串的时间复杂度同样为 O(n)。

空间复杂度：O(n)，其中 n 为字符串的长度。栈的大小不会超过 n，以及我们需要 O(n) 的空间记录括号的对应关系。

我们先定义一个pair，他用来储存每个括号对应的另一半括号的位置。
这个解法的关键点，就是他不使用先查找再反转的方式，而直接输出了反转后的内容。这个办法的核心思想是：
举例子s = “(u(love)i)”
我们能知道在最外层括号，是翻转一次，而最内层括号，是翻转后又反转的内容，所以最内层括号在加入到ret的时候是love。

让我们来模拟，当遍历s到第一个左括号的时候，他根据pair记录，查找到最外层有括号位置，然后遍历方向改变成向左，这时候遇到i，ret = “i”，然后遍历到内层有括号，索引转换到最内层左括号，方向向右，这时候一一推入’l’,‘o’,‘v’,‘e’，此时ret = “ilove”，然后遇到内层有括号，他根据pair将索引转换到内层左括号，方向向左，然后加入元素’u’，此时ret就是"iloveu"。然后遍历到外层左括号，索引转换到右括号，然后index再加上向右方向的step，此时index不再小于n，那么不会进入while循环。最后结果就是ret = “iloveu”。