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 慢慢做好了