aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--decode_string.c114
-rw-r--r--decode_string.py43
2 files changed, 157 insertions, 0 deletions
diff --git a/decode_string.c b/decode_string.c
new file mode 100644
index 0000000..c476cb9
--- /dev/null
+++ b/decode_string.c
@@ -0,0 +1,114 @@
+// 394. Decode String
+#include "leetcode.h"
+
+/*
+ * given an encoded string, return its decoded string. the encoding rule is
+ * 'k[encoded_string]' where the 'encoded_string' inside the square brackets is
+ * being repeated exactly 'k' times. note that 'k' is guaranteed to be a
+ * positive integer. you may assume that the input string is always valid; there
+ * are no extra white spaces, square brackets are well-formed, etc. furthermore,
+ * you may assume that the original data does not contain any digits, and that
+ * digits are only for those repeat numbers, 'k'. the test cases are generated
+ * such that the output will never exceed '10^5'.
+ */
+
+struct node_time {
+ int times;
+ struct node_time *next;
+};
+
+struct node_char {
+ char c;
+ struct node_char *next;
+};
+
+void push_int(struct node_time **head, int val) {
+ struct node_time *new = (struct node_time *)malloc(sizeof(struct node_time));
+ new->times = val;
+ new->next = *head;
+ *head = new;
+}
+
+void push_char(struct node_char **head, char c) {
+ struct node_char *new = (struct node_char *)malloc(sizeof(struct node_char));
+ new->c = c;
+ new->next = *head;
+ *head = new;
+}
+
+int pop_int(struct node_time **head) {
+ struct node_time *tmp = *head;
+ int res = tmp->times;
+ *head = (*head)->next;
+ free(tmp);
+ return res;
+}
+
+char pop_char(struct node_char **head) {
+ struct node_char *tmp = *head;
+ char res = tmp->c;
+ *head = (*head)->next;
+ free(tmp);
+ return res;
+}
+
+int word_size(struct node_char *head) {
+ int n = 0;
+ while (head) {
+ if (head->c == '[')
+ break;
+ n++;
+ head = head->next;
+ }
+ return n;
+}
+
+char *decodeString(char *s) {
+ struct node_time *int_stk = NULL;
+ struct node_char *char_stk = NULL;
+ int i = 0, n, k;
+ while (s[i]) {
+ if (s[i] >= '0' && s[i] <= '9') {
+ int num = atoi(&s[i]);
+ while (s[i] >= '0' && s[i] <= '9')
+ i++;
+ push_int(&int_stk, num);
+ } else if (s[i] > '9' && s[i] != ']') {
+ push_char(&char_stk, s[i]);
+ i++;
+ } else if (s[i] == '[') {
+ push_char(&char_stk, '[');
+ i++;
+ } else if (s[i] == ']') {
+ n = word_size(char_stk);
+ int times = pop_int(&int_stk);
+ char *word = (char *)malloc(n * sizeof(char));
+ for (k = 0; k < n; k++)
+ word[k] = pop_char(&char_stk);
+ pop_char(&char_stk);
+ for (; times; times--)
+ for (k = n - 1; k >= 0; k--)
+ push_char(&char_stk, word[k]);
+ free(word);
+ i++;
+ }
+ }
+ n = word_size(char_stk);
+ char *ans = (char *)calloc(n + 1, sizeof(char));
+ for (k = n - 1; k >= 0; k--)
+ ans[k] = pop_char(&char_stk);
+ return ans;
+}
+
+int main() {
+ char *s1 = "3[a]2[bc]", *s2 = "3[a2[c]]", *s3 = "2[abc]3[cd]ef";
+ char *ds1 = decodeString(s1);
+ char *ds2 = decodeString(s2);
+ char *ds3 = decodeString(s3);
+ printf("%s\n", ds1); // expect: aaabcbc
+ printf("%s\n", ds2); // expect: accaccacc
+ printf("%s\n", ds2); // expect: abcabccdcdcdef
+ free(ds1);
+ free(ds2);
+ free(ds3);
+}
diff --git a/decode_string.py b/decode_string.py
new file mode 100644
index 0000000..e62c5b0
--- /dev/null
+++ b/decode_string.py
@@ -0,0 +1,43 @@
+# 394. Decode String
+
+"""
+given an encoded string, return its decoded string. the encoding rule is
+'k[encoded_string]' where the 'encoded_string' inside the square brackets is
+being repeated exactly 'k' times. note that 'k' is guaranteed to be a
+positive integer. you may assume that the input string is always valid; there
+are no extra white spaces, square brackets are well-formed, etc. furthermore,
+you may assume that the original data does not contain any digits, and that
+digits are only for those repeat numbers, 'k'. the test cases are generated
+such that the output will never exceed '10^5'.
+"""
+
+
+class Solution(object):
+ def decodeString(self, s):
+ """
+ :type s: str
+ :rtype: str
+ """
+ stk, curr_int, curr_str = [], 0, ""
+ for c in s:
+ if c == "[":
+ stk.append(curr_str)
+ stk.append(curr_int)
+ curr_str = ""
+ curr_int = 0
+ elif c == "]":
+ num = stk.pop()
+ prev_str = stk.pop()
+ curr_str = prev_str + num * curr_str
+ elif c.isdigit():
+ curr_int = curr_int * 10 + int(c)
+ else:
+ curr_str += c
+ return curr_str
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.decodeString(s="3[a]2[bc]"))
+ print(obj.decodeString(s="3[a2[c]]"))
+ print(obj.decodeString(s="2[abc]3[cd]ef"))