Sponsored
Sponsored
Utilize a stack to handle the nested or paired parentheses efficiently. By pushing characters onto a stack until a closing parenthesis is encountered, then reversing the needed substring, you can leverage the stack's LIFO properties to achieve the desired result.
Time Complexity: O(n).
Space Complexity: O(n) due to the stack usage for storing characters.
1#include <iostream>
2#include <stack>
3using namespace std;
4
5string reverseParentheses(string s) {
6 stack<char> st;
7 for (char c : s) {
8 if (c != ')') st.push(c);
9 else {
10 string temp = "";
11 while (!st.empty() && st.top() != '(') {
12 temp += st.top();
13 st.pop();
14 }
15 st.pop(); // remove '('
16 for (char x : temp) st.push(x);
17 }
18 }
19 string result = "";
20 while (!st.empty()) {
21 result += st.top();
22 st.pop();
23 }
24 reverse(result.begin(), result.end());
25 return result;
26}
27
28int main() {
29 string s = "(u(love)i)";
30 cout << reverseParentheses(s) << endl;
31 return 0;
32}
33This C++ solution employs the STL stack to handle character storage, enabling the reversal of strings between parentheses effectively. By treating each closing parenthesis as an indicator to reverse the current stack contents until the matching open parenthesis is found, the algorithm can ensure correct nesting management.
This approach involves separately building the result string in a single pass using an auxiliary data structure to track position swaps. The use of local in-string reversals enables an efficient and clean traversal building mechanism.
Time Complexity: O(n).
Space Complexity: O(n), using additional space for parentheses pair tracking and intermediate char arrays.
In this Java solution, indexing is managed through an array for quick access and paired swaps during parsing. This enables a simplified build process that recognizes bracket positions and adjusts in a single iteration over the string.