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 Python variant applies indexed pair storage to identify parentheses boundaries for the two-pass construction. It offers a clean mechanism to trace and modify the sequence of characters accordingly, ensuring an efficient parsing and building process.