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 <stdio.h>
2#include <string.h>
3#include <stdlib.h>
4
5char* reverseParentheses(char* s) {
6 char stack[2000];
7 int top = -1;
8 int n = strlen(s);
9
10 for (int i = 0; i < n; i++) {
11 if (s[i] == ')') {
12 int start = top;
13 while (stack[top] != '(') top--;
14 top--; // pop '('
15 for (int k = start; k > top; k--)
16 stack[++top] = stack[k];
17 } else {
18 stack[++top] = s[i];
19 }
20 }
21 stack[top + 1] = '\0';
22 return strdup(stack);
23}
24
25int main() {
26 char s[] = "(u(love)i)";
27 char* result = reverseParentheses(s);
28 printf("%s\n", result);
29 free(result);
30 return 0;
31}
32This C solution uses an array-based stack to reverse substrings between parenthesis pairs. It iterates through the string, storing characters inside a stack until a closing parenthesis requires a substring reversal. The reversed substring is then pushed back onto the stack, achieving the desired sequence without parentheses.
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.
1
The JavaScript solution handles paired parenthesis index tracking through an object for dynamic access and simplifies character sequencing by toggling traversal direction at each parenthesis boundary, offering control with minimal execution complexity.