Leetcode Decode String problem solution

YASH PAL,

In this Leetcode Decode String problem solution you have 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].

Leetcode Decode String problem solution

Problem solution in Python.

class Solution(object):
    def decode_util(self, s, start):
        i = start
        curr_num = 0
        curr_str = ''
        
        while i < len(s):
            if s[i].isdigit():
                curr_num *= 10
                curr_num += int(s[i])
                i += 1
            elif s[i] in lowercase:
                curr_str += s[i]
                i += 1
            elif s[i] == '[':
                bracket_decode, last_idx = self.decode_util(s, i+1)
                curr_str += (curr_num * bracket_decode)
                i = last_idx + 1
                curr_num = 0
            elif s[i] == ']':
                break
            
        return curr_str, i
                
    
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        return self.decode_util(s, 0)[0]

Problem solution in Java.

class Solution {
    public String decodeString(String s) {
        StringBuilder sb = new StringBuilder();
        int count = 0;
        for (int i = 0; i <s.length();i++) {
            char c = s.charAt(i);
            if (c <= '9' && c >= '0') {
                count = count * 10 + c -'0';
            } else if (c == '[') {
                int j = i+1;
                int open = 1, close = 0;
                i++;
                while (i < s.length() && open != close) {
                    if (s.charAt(i) == '[') open++;
                    else if (s.charAt(i) == ']') close++;
                    i++;
                }
                String sub = decodeString(s.substring(j,--i));
                for (int f = 0; f < count;f++) {
                    sb.append(sub);
                }
                count = 0;
            } else {
                sb.append(c);
            }
        }
        
        return sb.toString();
    }
}

Problem solution in C++.

class Solution {
private:
    string selfConcat(const string& s, int times) {
        string out;
        
        for (int i = 0; i < times; ++i) {
            out.append(s);
        }
        
        return out;
    }
public:
    string decodeString(const string& s) {
        stack<int> multiplierS;
        stack<string> stringS;
        multiplierS.push(1);
        stringS.push("");
        
        int currMultiplier = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (isdigit(s[i])) {
                currMultiplier *= 10;
                currMultiplier += (s[i] - '0');
            } else if (s[i] == '[') {
                stringS.push("");
                multiplierS.push(currMultiplier);
                
                currMultiplier = 0;
            } else if (s[i] == ']') {
                int topMult = multiplierS.top(); multiplierS.pop();
                string topS = stringS.top(); stringS.pop();
                
                string decodedTop = selfConcat(topS, topMult);
                topS = stringS.top(); stringS.pop();
                
                stringS.push(topS + decodedTop);
            } else {
                stringS.top().push_back(s[i]);
            }
        }
        
        return stringS.top();
    }
};

Problem solution in C.

#define MAX_SIZE_STR_OUT 10000

char * helper(char *str_in,int *idx_in);

char * decodeString(char * s){
    if(!s)return NULL;
    char str_out[MAX_SIZE_STR_OUT];
    
    char * str_new;
    int idx_out=0,idx=0;
    
    while(s[idx]!=''){
        while((s[idx]>='a'&&s[idx]<='z')||(s[idx]>='A'&&s[idx]<='Z'))str_out[idx_out++]=s[idx++];
        str_new=helper(s,&idx);
        strcpy(&str_out[idx_out],str_new);
        idx_out+=strlen(str_new);
        free(str_new);  
    }
   
str_out[idx_out++]=0;    
char * str_ret = (char*)malloc(idx_out);
strcpy(str_ret,str_out);
return str_ret;
}


//to do remove the ' from strings

char *helper(char *str_in,int *idx_in){
    if(!str_in)return NULL;
    char * str_out = (char*)malloc(MAX_SIZE_STR_OUT);
    char * str_new;
    int idx_out=0,number =0,new_number=0;
    
    while(str_in[*idx_in]!=''){
        if((str_in[*idx_in]>='a'&&str_in[*idx_in]<='z')||
           (str_in[*idx_in]>='A'&&str_in[*idx_in]<='Z'))str_out[idx_out++]=str_in[*idx_in];
           
       else if(str_in[*idx_in]>='0'&&str_in[*idx_in]<='9'){
            new_number=0;
            if(!number){
                while(str_in[(*idx_in)]>='0'&&str_in[(*idx_in)]<='9'){
                new_number= new_number*10+(str_in[(*idx_in)]-'0');
                (*idx_in)++;
                }
                number =new_number;
            }
            else{
                str_new=helper(str_in,idx_in);
                strcpy(&str_out[idx_out],str_new);
                idx_out+=strlen(str_new);
                (*idx_in)--;
                free(str_new);
            }
        }
        
        else if(str_in[*idx_in]==']'){
            for(int i=0;i<number;i++)memcpy(&str_out[i*idx_out],str_out,idx_out);
            idx_out=number*idx_out+1;
            idx_out--;
            str_out[idx_out]=0;
            (*idx_in)++;
            return str_out;
        }
        (*idx_in)++;  
    }
str_out[idx_out]=0;
return str_out;
}

coding problems solutions