String compression and decompression for data set that can be nested

Question

My input is a compressed string of the format number[string] and the decompressed output form should be the string written number times. For example:

3[abc]4[ab]c = abcabcabcababababc

2[3[a]b] = aaabaaab.

My brute force approach in Java:

public class CompresnDecompresn {

    public static void main(String[] args) {

        String s="3[abc]4[ab]c";
        for (int i = 0; i<s.length(); i++)  {
            if(s.charAt(i)==']') {
                int j=i-1;
                while(true)  {
                    if(s.charAt(j)=='[') {
                        break;
                    }
                    j--;
                }
                int k=j-1;
                while(true) {
                    if(k<0) {
                        break;
                    }
                    int m=(int)s.charAt(k);
                    if(m<48 || m>57) {
                        break;
                    }
                    k--;
                }
                k++;
                int freq=Integer.parseInt(s.substring(k, j));
                String snippet=s.substring(j+1,i);
                String temp="";

                for (int l = 0; l < freq; l++) {
                    temp+=snippet;
                }
                s=s.substring(0,k)+temp+s.substring(i+1);
            }
        }        
        System.out.println(s);                
    }    
}

Can I get some better approach with less cost?

Answer 1

Since you use Java, feel free to use what Java offers to make the solution more readable and straightforward. Here takes Regex the place as well as concatenating String using the StringBuilder.

Consider the input String string ="3[abc]4[ab]c"; Personally, I'd go for something like this:

Firstly define the Couple class holding the pairs of number-letters.

private static class Couple {

    public int x;
    public String y;

    public Couple(int x, String y) {
        this.x = x;
        this.y = y;
    }
}

And here we go:

// Regex to extract the number before '[' and the content inside of '[]'
Pattern p = Pattern.compile("(\\d+)\\[(.*?)\\]");
Matcher m = p.matcher(string);

// Coupling the number and the letters
List<Couple> couples = new ArrayList<>();
while (m.find()) {
    couples.add(new Couple(Integer.parseInt(m.group(1)), m.group(2)));
}

// Concatenating String together using the for-cycle
String rest = string.substring(string.lastIndexOf("]")+1, string.length());
StringBuilder sb = new StringBuilder();

for (Couple c: couples) {
    for (int i=0; i<c.x; i++) {
        sb.append(c.y);
    }
}

// Enjoying the result
sb.append(rest);
System.out.println(sb.toString());

Please remember, this is just a dumb naïve solution to your problem working in case there is always the input string in the format of

number[string]number[string]number[string]rest // more of number[string] pairs

You have to think in wide whether there are places to be aware of failing code. What if there is no rest? What if the user's input will not be of the same format (never trust users' input) - so isn't it worth to validate it against Regex? You have to ask questions to yourself beggining with what if something happens.

Anyway, you can start on my implementation and go on as you need.