blob: e2103b656af976545f8f7b4fdf487ee7cd3c8228 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
// 1190. Reverse Substrings Between Each Pair of Parentheses
#include "leetcode.h"
/*
* you are given a string 's' that consists of lower case english letters and
* brackets. reverse the strings in each pair of matching parentheses, starting
* from the innermost one. your result should not contain any brackets.
*/
struct node {
int index;
struct node *next;
};
void qpush(struct node **top, int idx) {
struct node *n = (struct node *)malloc(sizeof(struct node));
n->index = idx;
n->next = NULL;
if (!(*top)) {
*top = n;
return;
}
n->next = *top;
*top = n;
return;
}
int qpop(struct node **top) {
if (!(*top))
return 0;
int x = (*top)->index;
*top = (*top)->next;
return x;
}
char *reverseParentheses(char *s) {
if (!s)
return "";
struct node *top = NULL;
for (int i = 0; i < strlen(s); i++) {
if (s[i] == '(')
qpush(&top, i);
else if (s[i] == ')') {
int beg = qpop(&top), end = i - 1;
s[beg] = ' ';
beg++;
while (beg < end) {
char c = s[beg];
s[beg] = s[end];
s[end] = c;
beg++, end--;
}
s[i] = ' ';
}
}
int j = 0;
for (int i = 0; i < strlen(s); i++)
if (s[i] != ' ')
s[j++] = s[i];
s[j] = '\0';
return s;
}
int main() {
char s1[] = "(abcd)", s2[] = "(u(love)i)", s3[] = "(ed(et(oc))el)";
printf("%s\n", reverseParentheses(s1)); // expect: dcba
printf("%s\n", reverseParentheses(s2)); // expect: iloveu
printf("%s\n", reverseParentheses(s3)); // expect: leetcode
}
|