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.
1def reverseParentheses(s):
2 stack = []
3 for char in s:
4 if char == ')':
5 queue = []
6 while stack and stack[-1] != '(':
7 queue.append(stack.pop())
8 stack.pop() # pop '('
9 stack.extend(queue)
10 else:
11 stack.append(char)
12 return ''.join(stack)
13
14
15s = '(u(love)i)'
16print(reverseParentheses(s))
17This Python implementation uses a list as a stack to reverse parts of the string contained between parentheses. By popping off characters and utilizing a temporary storage list, it reverses the sequence efficiently and appends it back onto the original processing stack.
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.
using System.Collections.Generic;
public class ReverseParentheses {
public string ReverseParentheses(string s) {
Stack<int> stack = new Stack<int>();
int[] pair = new int[s.Length];
for (int i = 0; i < s.Length; i++) {
if (s[i] == '(') stack.Push(i);
else if (s[i] == ')') {
int j = stack.Pop();
pair[i] = j;
pair[j] = i;
}
}
char[] result = new char[s.Length];
int idx = 0, dir = 1;
for (int i = 0; i < s.Length; i += dir) {
if (s[i] == '(' || s[i] == ')') {
i = pair[i];
dir = -dir;
} else {
result[idx++] = s[i];
}
}
return new string(result, 0, idx);
}
public static void Main(string[] args) {
ReverseParentheses rp = new ReverseParentheses();
Console.WriteLine(rp.ReverseParentheses("(ed(et(oc))el)"));
}
}
This C# implementation uses an array for parenthesis pair tracking and a stack for real-time index management. The strategic index skipping and direct character assignment minimize additional restructuring operations.