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.
1import java.util.Stack;
2
3public class ReverseParentheses {
4 public String reverseParentheses(String s) {
5 Stack<Character> stack = new Stack<>();
6 for (char c : s.toCharArray()) {
7 if (c != ')') stack.push(c);
8 else {
9 StringBuilder sb = new StringBuilder();
10 while (stack.peek() != '(') {
11 sb.append(stack.pop());
12 }
13 stack.pop(); // pop '('
14 for (char rc : sb.toString().toCharArray()) stack.push(rc);
15 }
16 }
17 StringBuilder result = new StringBuilder();
18 while (!stack.isEmpty()) result.append(stack.pop());
19 return result.reverse().toString();
20 }
21
22 public static void main(String[] args) {
23 ReverseParentheses rp = new ReverseParentheses();
24 System.out.println(rp.reverseParentheses("(u(love)i)"));
25 }
26}
27This Java solution uses a stack to efficiently reverse substrings within parentheses. By iteratively processing the string and using the stack to manage open and close parenthesis contexts, it provides a clean logic flow to manage reversal operations appropriately.
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.
This C solution divides the task into first creating pair indices for easy traversal and reversal through position swapping, enabling an efficient processing path that aligns with the stack-based idea but applied to index transformations and direct character use.