【算法题】14.字符串解码

题目

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例1:

s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

解析：

1. 遍历字符，将非]字符入栈。
2. 遇到]后，循环出栈直到[,将中间的字母字符串缓存。
3. 继续循环出栈[前的数字，遇到非数组结束，将数字和缓存的字母字符串解码，将其入栈。
4. 循环上述操作，至字符串遍历结束。

复杂度分析：

时间复杂度：
空间复杂度：

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

char * decodeString(char * s){
   int len = strlen(s);
   
   int stackSize = 50;
   char* stack = (char*)malloc(stackSize * sizeof(char));
   int top = -1;
   
   for (int i = 0; i < len; ++i) {
       //若不等于]则入栈
       if (s[i] != ']') {
           if (top == stackSize - 1) {
               stack = realloc(stack, (stackSize += 50) * sizeof(char));
           }
           stack[++top] = s[i];
       }
       //若等于 则遍历出栈 直到为'['，将其解码，并入栈。
       else {
           int tempSize = 10;
           char* temp = (char*)malloc(tempSize * sizeof(char));
           int topOfTemp = -1;
           while (stack[top] != '[') {
               if (topOfTemp == tempSize - 1) {
                   temp = realloc(temp, (tempSize += 10) * sizeof(char));
               }
               temp[++topOfTemp] = stack[top--];
           }
           int kLength = 0;
           double repeatCount = 0;
           top--;
           while (top != -1 && stack[top] >= '0' && stack[top] <= '9') {
               kLength = pow(10.00,repeatCount) * (stack[top] - '0');
               repeatCount = repeatCount + 1;
               top--;
           }

           for (int k = 0; k < kLength; ++k) {
               int kk = topOfTemp;
               while (kk != -1) {
                   if (top == stackSize - 1) {
                       stack = realloc(stack, (stackSize += 50) * sizeof(char));
                   }
                   stack[++top] = temp[kk--];
               }
           }
           free(temp);
           temp = NULL;
       }
   }
   char* ans = realloc(stack, (top + 2) * sizeof(char));
   ans[++top] = '\0';
   return ans;
}