2024-07-11
1190. Reverse Substrings Between Each Pair of Parentheses
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.
直觉是stack或recursive
一路走过去
发现需要处理的起始符就push一层新的
发现终止符就把中间处理一下 pop 出去
string reverseParentheses(string s) {
if (s.size() == 1) {
return s;
}
vector<string> tmp(1);
size_t new_idx = 0;
for (char c : s) {
if ('(' == c) {
tmp.push_back("");
}
else if (')' == c) {
reverse(tmp.back().begin(), tmp.back().end());
if (1 == tmp.size()) {
return tmp.back();
}
string r = tmp.back();
tmp.pop_back();
tmp.back() = tmp.back() + r;
}
else {
tmp.back().push_back(c);
}
}
return tmp.back();
}
因为要沿着走n个char
每次触发reverse 是O(n)
worst case 会是 n + (n-2) + ... 共 n/2 项
O(n^2)
实际上会发现中间很多个会来回重复倒
如果是 "()" 会倒一次
如果是 "(())" 中间的 '(' ')' 会倒两次等于正走
所以可以先扫过去看每组起始跟终止位置
在正走的时候碰到'('就跳过去对应的')'开始倒走
倒走的时候碰到')'就跳回对应的'('变正走(=倒倒走)
这样可以压到 O(n)
但是看了解答以后
虽然跟我想的一样
我觉得我还是用 string statck 慢慢做好了