一个 trick的O(n)解法,每次遇到括号,则跳转到对应的括号,同时改变遍历方向。字母则直接拼接到后面,即可
普通方法见方法2
ref{:target=”_blank”}
C++ 代码
方法1
class Solution {
public:
string reverseParentheses(string s) {
unordered_map<int,int> h;
stack<int> stk;
int n = s.size();
// 计算左右括号的映射关系
for(int i=0; i<n; ++i) {
char c = s[i];
if('(' == c)stk.push(i);
else if(')' == c) {
h[stk.top()] = i;
h[i] = stk.top();
stk.pop();
}
}
// 遇到括号找对应的括号下标,并修改遍历方向
// 其他字母直接拼接
string res;
for(int i=0,d=1; i<n; i += d) {
char c = s[i];
if('(' == c || ')' == c) {
d = -d;
i = h[i];
} else {
res += c;
}
}
return res;
}
};
方法2
常规解法,按照定义求解,time:O(n^2)
遇到右括号则弹出计算,其他情况字符入栈
class Solution {
public:
string reverseParentheses(string s) {
string res;
for(int i=0; i<s.size(); ++i) {
char c = s[i];
if(')' == c) {
string tmp;
while(res.size() && res.back() != '(') {
tmp += res.back();
res.pop_back();
}
res.pop_back();
res += tmp;
} else {
// ( 和 字母入栈
res.push_back(c);
}
}
return res;
}
};