diff options
Diffstat (limited to 'reverse_substr_parentheses.c')
-rw-r--r-- | reverse_substr_parentheses.c | 69 |
1 files changed, 69 insertions, 0 deletions
diff --git a/reverse_substr_parentheses.c b/reverse_substr_parentheses.c new file mode 100644 index 0000000..e2103b6 --- /dev/null +++ b/reverse_substr_parentheses.c @@ -0,0 +1,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 +} |