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;
}
Please provide your comments.
