# 394. Decode String
###### tags: `Medium`
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; 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. For example, there won't be input like 3a or 2[4].

##### Example 1:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

##### Example 2:

Input: s = "3[a2[c]]"
Output: "accaccacc"

##### Example 3:

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

##### Example 4:

Input: s = "abc3[cd]xyz"
Output: "abccdcdcdxyz"

##### Constraints:
* 1 <= s.length <= 30
* s consists of lowercase English letters, digits, and square brackets '[]'.
* s is guaranteed to be a valid input.
* All the integers in s are in the range [1, 300].
---

### Mine:

> Runtime: 0 ms, faster than 100.00% of C online submissions for Decode String.
> Memory Usage: 6.1 MB, less than 71.11% of C online submissions for Decode String.

每個node使用一個array紀錄其內組成的字串

| times | str | *node |
| -------- | -------- | -------- |
| 重複的次數，如果是-1則代表這是一個char並且只重複一次，如果是正整數則是代表node(括號內的字串)重複的次數 | 儲存char | 指向另一個node的ptr，代表著更下一層的字串 |

parseStr() 將字串處理為「重複幾次」的「小字串或字母」
decStr() 讀取node並重組成一個完整的答案句子

typedef struct Node N;
struct Node {
    int   times[30];
    N    *node[30];
    char  str[30];
};

int parseStr(char* s, N* pN)
{
    if ( s == NULL) return 0;
    if (*s == '\0') return 0;
    
    int i   = 0;
    int len = 0;
    
    while(1) {
        char c = *s;
        
        /* detect the number before brackets */
        if (isdigit(c)) {
            char* p_start = strchr(s, '[');
            
            /* make this a string, prepare for atoi */
            *p_start = '\0';
            pN->times[i] = atoi(s);
            
            /* make a new node for child string inside the brackets */
            pN->node[i] = malloc(sizeof(N));
            memset(pN->node[i], 0, sizeof(N));
            
            /* get the len of child string, and jump through it. */
            int ChildLen = parseStr(p_start +1, pN->node[i]);
            
            /* also note the len of string in current brackets */
            len += p_start + ChildLen +1 /*]*/ -s +1;
            s = p_start + ChildLen +1;
            
        } else {
            /* no brackets, then simply remember the char here */
            pN->str[i] = c;
            
            /* -1 is a symbol, mean that there's one char to add */
            pN->times[i] = -1;
            
            /* also note the len of string in current brackets */
            len++;
        }
        
        i++;
        s++;
        if (*s == '\0') break;
        if (*s == ']')  break;
    }
    
    return len;
}

void decStr(char* s, N* pN)
{
    if (s  == NULL) return;
    if (pN == NULL) return;
    
    int i = 0;
    
    while (1) {
        /* 0 == no more data */
        if (pN->times[i] == 0) {
            break;
            
        /* -1 means need to add one char into string */
        } else if (pN->times[i] == -1) {
            strncat(s, &pN->str[i], 1);
            s++;
            
        /* other value means there's valid node, and need to repeat pN->times[i] times */
        } else {
            for (int j = 0; j < pN->times[i]; j++) {
                decStr(s, pN->node[i]);
            }
        }
        i++;
    }
}

char * decodeString(char * s)
{
    /* parse origin string */    
    N root = {0};
    parseStr(s, &root);
    
    /* allocate buffer for answer */
    char* ret = calloc(2000, sizeof(char));
    memset(ret, 0, 2000*sizeof(char));
    
    /* decode the node we made */
    decStr(ret, &root);
    
    return ret;  

}

### Other best solution

// Submitted by Samy Vilar on 06/13/2021
char *decodeString(char *self) {
    static char 
        solution[100000];
    
    static unsigned 
        history[15];
    
    static size_t
        bases[15];
    
    size_t 
        at, tail = 1, delta, 
        factor = 0;        
    
    for (at = (tail = 0); *self; self++) 
        if (*self > '0' && *self <= '9') {
            bases[tail] = at;
            history[tail++] = factor;
            for (factor = (*self++ - '0'); *self != '['; 
                 factor = (factor * 10) + (*self++ - '0'));                        
        } else if (*self == ']') {            
            if (at != bases[--tail])
                for (delta = at - bases[tail]; --factor; at += delta)
                    memcpy(&solution[at], &solution[at - delta], delta);            
            factor = history[tail];
        } else 
            solution[at++] = *self;        
    
    solution[at] = '\0';
    return solution;
}