aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--reverse_substr_parentheses.c69
-rw-r--r--reverse_substr_parentheses.py31
2 files changed, 100 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
+}
diff --git a/reverse_substr_parentheses.py b/reverse_substr_parentheses.py
new file mode 100644
index 0000000..499515d
--- /dev/null
+++ b/reverse_substr_parentheses.py
@@ -0,0 +1,31 @@
+# 1190. Reverse Substrings Between Each Pair of Parentheses
+
+"""
+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.
+"""
+
+
+class Solution(object):
+ def reverseParentheses(self, s):
+ """
+ :type s: str
+ :rtype: str
+ """
+ ans = [""]
+ for c in s:
+ if c == "(":
+ ans.append("")
+ elif c == ")":
+ ans[len(ans) - 2] += ans.pop()[::-1]
+ else:
+ ans[-1] += c
+ return "".join(ans)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.reverseParentheses(s="(abcd)"))
+ print(obj.reverseParentheses(s="(u(love)i)"))
+ print(obj.reverseParentheses(s="(ed(et(oc))el)"))