# 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.

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

This problem is so complicated. My attempt is not successful. 2nd attempt is faster but a little lengthy solution with multiple dynamic allocations.
Wanted to reduce code size and reduce dynamic allocations. Finally could do by learning from approach 2 and other solutions.

Below is my lengthy solution:

`/* stk node which can either contain string or number,    in case of string , the pointer can be pointing to input or newly allocated one */struct stknode{    char type; // number(1) or string (2)    union {        int num;        struct strng{            char *str;            int len;            bool alloc;        }st;    };};struct stk{    struct stknode *stk_ar;    int curidx;     int stksz;// current stk allocated size};#define STK_INIT_SIZE 100struct stk *stk_create(int size){    struct stk *stkp;    stkp = (struct stk *)calloc(1, sizeof(struct stk));    stkp->stk_ar = (struct stknode *)calloc(size, sizeof(struct stknode));    stkp->stksz = size;    return stkp;}int stk_push(struct stk *s, struct stknode *nd){    if (s->curidx >= s->stksz){        s->stksz += STK_INIT_SIZE;        s->stk_ar = (struct stknode *)realloc(s->stk_ar, s->stksz*sizeof(struct stknode));    }    s->stk_ar[s->curidx] = *nd;    s->curidx++;    return 0;}int stk_pop(struct stk *s, struct stknode *nd){    if (!s->curidx)        return -1;    s->curidx--;    *nd = s->stk_ar[s->curidx];    return 0;}int stk_empty(struct stk *s){    return (!(s->curidx));}int stk_top(struct stk *s, struct stknode *nd){    if (s->curidx)         *nd = s->stk_ar[s->curidx-1];    return (s->curidx);}void copy_to_res(char **res, int *resind, int *reslen, char *data,                int sz){    char *ores = *res;        if (((*resind) + sz) > (*reslen)){        int incsz = (sz > 1200) ? sz : 1200;        ores =  (char *)realloc(ores, (*reslen)+incsz);        // todo malloc check        *reslen = (*reslen)+incsz;    }    memcpy(ores+(*resind), data, sz);    (*resind) += sz;    *res = ores;    return;}void str_push_or_add_2res(char *str, int stlen, char **res, int *resind, int *reslen, struct stk *stk, bool free_str){    /* string extracted from input */    /* add to stk or add to result if stk is empty */    if (stk_empty(stk)){        if (stlen){            copy_to_res(res, resind, reslen, str, stlen);            if (free_str) free(str); }        return;    }    struct stknode nd;    nd.type = 2; nd.st.str = str; nd.st.alloc = free_str; nd.st.len = stlen;    stk_push(stk, &nd);    return;}char* combine_strings(char *st1, int len1, char *st2, int len2, int *ol){    char *cst;    *ol = len1+len2;    cst = (char *)malloc((*ol)*sizeof(char));    if (st1)        memcpy(cst, st1, len1);    if (st2)        memcpy(cst+len1, st2, len2);    return cst;}char *get_dec_str(int num, char *st, int len, int *olen){    char *res = NULL, *tmp;    int ii, patlen =  0;    if (len && num) patlen = len*num;    *olen = patlen;    if (!patlen)        return NULL;    res = (char *)malloc(patlen*sizeof(char));    tmp = res;    for (ii=0; ii<num; ii++){        memcpy(tmp, st, len);        tmp += len;    }    return res;}int get_num(char *s, int *ind){    int ii = *ind, num=0;    while (isdigit(s[ii])){        num = num*10+(s[ii]-'0');        ii++;    }    *ind = ii;    return num;}char* get_str(char *s, int *ind, int *st_len){    int ii = *ind, slen =0;    char *res = s+ii;    while (s[ii] >= 'a' && s[ii] <= 'z'){        ii++, slen++;    }    *ind = ii;    *st_len = slen;    if (!slen) return NULL;    return res;}char * decodeString(char * s){    int ii,jj, reslen=1200, resind=0,num=0, patlen =0, stlen;    struct stk *stk;    struct stknode nd, nd1;    char *res, *str = NULL;    stk = stk_create(STK_INIT_SIZE);    res = (char *)calloc(reslen, sizeof(char));    for (ii=0; s[ii]!='\0'; ii++){        /* if char is digit */        if (isdigit(s[ii])){            num =  get_num(s, &ii); ii--;        }        else if (s[ii] >= 'a' && s[ii] <= 'z'){            str = get_str(s, &ii, &stlen);            str_push_or_add_2res(str, stlen, &res, &resind, &reslen, stk, 0);            ii--;        }        else if (s[ii] == '['){            nd.type = 1; nd.num = num; num = 0;            stk_push(stk, &nd);        } else if (s[ii] == ']'){ char *cs; int cslen;            /* pop str */            stk_pop(stk, &nd);            stk_pop(stk, &nd1);            /* pop till we get number element */            while (nd1.type==2){                /* combine strings */                cs = combine_strings(nd1.st.str, nd1.st.len, nd.st.str, nd.st.len, &cslen);                if (nd.st.alloc) free(nd.st.str);                nd.st.str = cs; nd.st.len = cslen; nd.st.alloc = 1;                stk_pop(stk, &nd1);            }            /* here we have string and number */            char *dec_str; int ds_len;            dec_str = get_dec_str(nd1.num, nd.st.str, nd.st.len, &ds_len);            if (nd.st.alloc)  free(nd.st.str);            str_push_or_add_2res(dec_str, ds_len, &res, &resind, &reslen, stk, 1);        }     }    if (resind <= reslen)        res[resind]='\0';    else{        printf("todo reallocate res\n********");    }    return res;}`

My next solution:

• Here I have used 2 stacks for number and string.
• String stack contains the index to the result.
• Directly copying the pattern to the result , then making use of those indices to save the locations in string stack.
• This solution does not have any limitations of stack size, result sizes.
`struct stknode{    int val;};struct stk{    struct stknode *stk_ar;    int curidx;     int stksz;// current stk allocated size};#define STK_INIT_SIZE 100struct stk *stk_create(int size){    struct stk *stkp;    stkp = (struct stk *)calloc(1, sizeof(struct stk));    stkp->stk_ar = (struct stknode *)calloc(size, sizeof(struct stknode));    stkp->stksz = size;    return stkp;}int stk_push(struct stk *s, struct stknode *nd){    if (s->curidx >= s->stksz){        s->stksz += STK_INIT_SIZE;        s->stk_ar = (struct stknode *)realloc(s->stk_ar, s->stksz*sizeof(struct stknode));    }    s->stk_ar[s->curidx] = *nd;    s->curidx++;    return 0;}int stk_pop(struct stk *s, struct stknode *nd){    if (!s->curidx)        return -1;    s->curidx--;    *nd = s->stk_ar[s->curidx];    return 0;}int stk_empty(struct stk *s){    return (!(s->curidx));}int stk_top(struct stk *s, struct stknode *nd){    if (s->curidx)         *nd = s->stk_ar[s->curidx-1];    return (s->curidx);}int get_num(char *s, int *ind){    int ii = *ind, num=0;    while (isdigit(s[ii])){        num = num*10+(s[ii]-'0');        ii++;    }    *ind = ii;    return num;}void copy_to_res(char **res, int *resind, int *reslen, int data_ind,                int sz, int ntimes){    char *ores = *res;    char *data ;    if (((*resind) + (sz*ntimes)) > (*reslen)){        int incsz = (sz*ntimes > 1200) ? sz*ntimes : 1200;        ores =  (char *)realloc(ores, (*reslen)+incsz);        // todo malloc check        *reslen = (*reslen)+incsz;    }    data = ores + data_ind;    for (int ii=0; ii<ntimes; ii++){        memcpy(ores+(*resind), data, sz);        (*resind) += sz;    }    *res = ores;    return;}void copy_str2res(char *s, int *ind, int *st_len,                  char **res, int *resind, int *reslen){    int ii = *ind, slen =0;    char *strt = s+ii;    while (s[ii] >= 'a' && s[ii] <= 'z'){        ii++, slen++;    }    *ind = ii;    *st_len = slen;    char *ores = *res;    if (((*resind) + (slen)) > (*reslen)){        int incsz = (slen > 1200) ? slen : 1200;        ores =  (char *)realloc(ores, (*reslen)+incsz);        // todo malloc check        *reslen = (*reslen)+incsz;    }    memcpy(ores+(*resind), strt, slen);    (*resind) += slen;    *res = ores;    return;}char * decodeString(char * s){    int ii,jj, reslen=1200, resind=0,num=0, patlen =0, stlen;    struct stk *numstk, *strstk;    struct stknode nd;    char *res;    /* create 2 stacks : numbers and strings */    numstk = stk_create(STK_INIT_SIZE);    strstk = stk_create(STK_INIT_SIZE);    res = (char *)calloc(reslen, sizeof(char));    for (ii=0; s[ii]!='\0'; ii++){        /* if char is digit , get the number*/        if (isdigit(s[ii])){            num =  get_num(s, &ii); ii--;        }        /* if char is alphabet, get the string length and copy it to result */         else if (s[ii] >= 'a' && s[ii] <= 'z'){            copy_str2res(s, &ii, &stlen, &res, &resind, &reslen);            ii--;        }        else if (s[ii] == '['){            /* push number */            nd.val = num; num = 0;            stk_push(numstk, &nd);            /* push current index of the result */            nd.val = resind;            stk_push(strstk, &nd);        } else if (s[ii] == ']'){            /* pop number */            stk_pop(numstk, &nd);            num = nd.val;            /* pop the index of the result when string pointed to '[' */            stk_pop(strstk, &nd);            /* the current index is resind where the current string is copied                from previous index nd.val (stk element) till the resind */            /* this current string should be duplicated to num-1 times as                it is already copied one time in result*/            /*note this sometimes the number can be 1,              in these we need to any copy. eg. 3[1[ab]], 3[aa4[]] */            if (num-1 && (resind-nd.val))                copy_to_res(&res, &resind, &reslen, nd.val, resind-nd.val, num-1);        }    }            if (resind <= reslen)        res[resind]='\0';    else{        printf("TODO reallocate res\n********");    }    return res;       }`