题目描述
给出一个字符串 s
(仅含有小写英文字母和括号)。
请你按照从括号内到外的顺序,逐层反转每对匹配括号中的字符串,并返回最终的结果。
注意,您的结果中 不应 包含任何括号。
样例
输入:s = "(abcd)"
输出:"dcba"
输入:s = "(u(love)i)"
输出:"iloveu"
输入:s = "(ed(et(oc))el)"
输出:"leetcode"
输入:s = "a(bcdefghijkl(mno)p)q"
输出:"apmnolkjihgfedcbq"
限制
0 <= s.length <= 2000
s
中只有小写英文字母和括号。- 我们确保所有括号都是成对出现的。
算法1
(栈) $O(n^2)$
- 用栈结构,遇到左括号或者字符,则进栈;遇到右括号,则弹栈栈顶字母直到左括号,然后再把弹出的字母放入到栈中。
- 最后输出整个栈的序列(从栈底到栈顶)即可。
时间复杂度
- 每个字符最多进栈一次,出栈一次,但可能被反转 $O(n)$ 次,故时间复杂度为 $O(n^2)$。最坏情况例如
a(b(c(d(e(...)))))
。
空间复杂度
- 需要 $O(n)$ 的额外空间存储临时字符串和答案。
C++ 代码
class Solution {
public:
string reverseParentheses(string s) {
string res;
for (char c : s) {
if (c == '(') {
res.push_back(c);
} else if (c == ')') {
string tmp;
while (res.back() != '(') {
tmp += res.back();
res.pop_back();
}
res.pop_back();
res += tmp;
} else {
res.push_back(c);
}
}
return res;
}
};
算法2
(按路径遍历) $O(n)$
- 算法 1 显然是频繁反转临时字符串导致时间浪费。这个算法避免了字符串反转,而是采用了根据特定顺序遍历的方式一次拼装字符串。
- 先使用栈求出每个括号对应匹配括号的下标 $pos$。
- 从 $0$ 位置开始遍历,初始定向为正向。如果遍历过程中遇到了左括号或者右括号,则跳转到当前括号对应括号的位置,并且将方向取反。否则,拼装当前遇到的字符串。
时间复杂度
- 预处理 $pos$ 的时间复杂度为 $O(n)$。
- 遍历时,每个字符仅被访问一次,故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储预处理数组,栈以及答案。
C++ 代码
class Solution {
public:
string reverseParentheses(string s) {
const int n = s.size();
stack<int> st;
vector<int> pos(n);
for (int i = 0; i < n; i++) {
if (s[i] == '(') {
st.push(i);
} else if (s[i] == ')') {
pos[st.top()] = i;
pos[i] = st.top();
st.pop();
}
}
int dir = 1;
string ans;
for (int i = 0; i < n; i += dir) {
if (s[i] == '(' || s[i] == ')') {
i = pos[i];
dir = -dir;
} else {
ans += s[i];
}
}
return ans;
}
};
子辰助教yyds
报告 格式错了
复杂度已修正,之后给出 $O(n)$ 的算法
线性算法已更新
真不戳 子辰