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.
The JavaScript solution uses an array functioning as a stack to manage the sequence assembly and reversal process. It offers efficient character stacking and substring reversal through JavaScript's flexible array structure, enhancing the code's readability and maintainability.
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#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5void reverse(char *s, int start, int end) {
6 while (start < end) {
7 char temp = s[start];
8 s[start] = s[end];
9 s[end] = temp;
10 start++;
11 end--;
12 }
13}
14
15char* reverseParentheses(char* s) {
16 int len = strlen(s);
17 int *pair = malloc(len * sizeof(int));
18 int *stack = malloc(len * sizeof(int));
19 int top = -1;
20
21 for (int i = 0; i < len; i++) {
22 if (s[i] == '(') {
23 stack[++top] = i;
24 } else if (s[i] == ')') {
25 int j = stack[top--];
26 pair[i] = j;
27 pair[j] = i;
28 }
29 }
30
31 char *result = malloc(len + 1);
32 int idx = 0, dir = 1;
33 for (int i = 0; i < len; i += dir) {
34 if (s[i] == '(' || s[i] == ')') {
35 i = pair[i];
36 dir = -dir;
37 } else {
38 result[idx++] = s[i];
39 }
40 }
41 result[idx] = '\0';
42 free(pair);
43 free(stack);
44
45 return result;
46}
47
48int main() {
49 char s[] = "(ed(et(oc))el)";
50 char* result = reverseParentheses(s);
51 printf("%s\n", result);
52 free(result);
53 return 0;
54}
55This 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.
Solve with full IDE support and test cases