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?
Advertisement
Answer
We actually want to find the strings in [] and repeat it n times which is specified before the []. But the problem is these strings are nested.
So when we call the function that reads the string in[] it should call itself again when it hits a new []. Hence this leads to a recursive solution and we loop through the input string only once.
public class StringDecomposer {
public String process(String input) {
StringBuilder result = new StringBuilder();
decompres(input, 0, result);
return result.toString();
}
private int decompres(String input, int ofset, StringBuilder result) {
StringBuilder rpt = new StringBuilder();
StringBuilder current = new StringBuilder();
while(ofset < input.length()) {
if(input.charAt(ofset) == '[') {
ofset = decompres(input, ofset+1, current);
repeat(rpt, current);
result.append(current);
rpt.delete(0, rpt.length());
current.delete(0, current.length());
}
else if(input.charAt(ofset) == ']') {
break;
}
else if(input.charAt(ofset) > 47 &&
input.charAt(ofset) < 58) {
rpt.append(input.charAt(ofset));
}
else {
current.append(input.charAt(ofset));
}
ofset++;
}
result.append(current);
return ofset;
}
private void repeat(StringBuilder rpt, StringBuilder input) {
if(rpt.length() > 0) {
StringBuilder current = new StringBuilder(input);
int times = Integer.parseInt(rpt.toString());
for(int i = 1; i < times; i++) {
input.append(current);
}
}
}
}