Optimal algorithm for this string decompression

Question

I have been working on an exercise from google's dev tech guide. It is called Compression and Decompression you can check the following link to get the description of the problem Challenge Description.

Here is my code for the solution:

public static String decompressV2 (String string, int start, int times) {
    String result = "";
    for (int i = 0; i < times; i++) {
        inner:
        {
            for (int j = start; j < string.length(); j++) {
                if (isNumeric(string.substring(j, j + 1))) {
                    String num = string.substring(j, j + 1);
                    int times2 = Integer.parseInt(num);
                    String temp = decompressV2(string, j + 2, times2);
                    result = result + temp;
                    int next_j = find_next(string, j + 2);
                    j = next_j;
                    continue;
                }
                if (string.substring(j, j + 1).equals("]")) {  // Si es un bracket cerrado
                    break inner;
                }

                result = result + string.substring(j,j+1);
            }
        }
    }
    return result;
}

public static int find_next(String string, int start) {
    int count = 0;
    for (int i = start; i < string.length(); i++) {
        if (string.substring(i, i+1).equals("[")) {
            count= count + 1;
        }
        if (string.substring(i, i +1).equals("]") && count> 0) {
            count = count- 1;
            continue;
        }
        if (string.substring(i, i +1).equals("]") && count== 0) {
            return i;
        }
    }
    return -111111;
}

I will explain a little bit about the inner workings of my approach. It is a basic solution involves use of simple recursion and loops.

So, let's start from the beggining with a simple decompression:

DevTech.decompressV2("2[3[a]b]", 0, 1);

As you can see, the 0 indicates that it has to iterate over the string at index 0, and the 1 indicates that the string has to be evaluated only once: 1[ 2[3[a]b] ]

The core here is that everytime you encounter a number you call the algorithm again(recursively) and continue where the string insides its brackets ends, that's the find_next function for.

When it finds a close brackets, the inner loop breaks, that's the way I choose to make the stop sign.

I think that would be the main idea behind the algorithm, if you read the code closely you'll get the full picture.

So here are some of my concerns about the way I've written the solution:

I could not find a more clean solution to tell the algorithm were to go next if it finds a number. So I kind of hardcoded it with the find_next function. Is there a way to do this more clean inside the decompress func ?
About performance, It wastes a lot of time by doing the same thing again, when you have a number bigger than 1 at the begging of a bracket.
I am relatively to programming so maybe this code also needs an improvement not in the idea, but in the ways It's written. So would be very grateful to get some suggestions.
This is the approach I figure out but I am sure there are a couple more, I could not think of anyone but It would be great if you could tell your ideas.
In the description it tells you some things that you should be awared of when developing the solutions. They are: handling non-repeated strings, handling repetitions inside, not doing the same job twice, not copying too much. Are these covered by my approach ?
And the last point It's about tets cases, I know that confidence is very important when developing solutions, and the best way to give confidence to an algorithm is test cases. I tried a few and they all worked as expected. But what techniques do you recommend for developing test cases. Are there any softwares?

So that would be all guys, I am new to the community so I am open to suggestions about the how to improve the quality of the question. Cheers!

I think your question is a better fit for codereview.stackexchange.com . Stackoverflow tends to prefer questions that have a single clear right answer. See stackoverflow.com/help/on-topic — Paul Hankin
– Paul Hankin, Commented Apr 10, 2020 at 7:34

Matt Timmermans · Accepted Answer · 2020-04-10 13:21:10Z

3

Your solution involves a lot of string copying that really slows it down. Instead of returning strings that you concatenate, you should pass a StringBuilder into every call and append substrings onto that.

That means you can use your return value to indicate the position to continue scanning from.

You're also parsing repeated parts of the source string more than once.

My solution looks like this:

public static String decompress(String src)
{
    StringBuilder dest = new StringBuilder();
    _decomp2(dest, src, 0);
    return dest.toString();
}

private static int _decomp2(StringBuilder dest, String src, int pos)
{
    int num=0;
    while(pos < src.length()) {
        char c = src.charAt(pos++);
        if (c == ']') {
            break;
        }
        if (c>='0' && c<='9') {
            num = num*10 + (c-'0');
        } else if (c=='[') {
            int startlen = dest.length();
            pos = _decomp2(dest, src, pos);
            if (num<1) {
                // 0 repetitions -- delete it
                dest.setLength(startlen);
            } else {
                // copy output num-1 times
                int copyEnd = startlen + (num-1) * (dest.length()-startlen);
                for (int i=startlen; i<copyEnd; ++i) {
                    dest.append(dest.charAt(i));
                }
            }
            num=0;
        } else {
            // regular char
            dest.append(c);
            num=0;
        }
    }
    return pos;
}

answered Apr 10, 2020 at 13:21

Matt Timmermans

60.9k3 gold badges57 silver badges106 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

גלעד ברקן Over a year ago

Nice. I like the idea of updating a number rather than accumulating a string and converting.

גלעד ברקן · Accepted Answer · 2020-04-10 12:33:18Z

I would try to return a tuple that also contains the next index where decompression should continue from. Then we can have a recursion that concatenates the current part with the rest of the block in the current recursion depth.

Here's JavaScript code. It takes some thought to encapsulate the order of operations that reflects the rules.

function f(s, i=0){
  if (i == s.length)
    return ['', i];
    
  // We might start with a multiplier
  let m = '';
  while (!isNaN(s[i]))
    m = m + s[i++];

  // If we have a multiplier, we'll
  // also have a nested expression
  if (s[i] == '['){
    let result = '';
    const [word, nextIdx] = f(s, i + 1);
    for (let j=0; j<Number(m); j++)
      result = result + word;
    const [rest, end] = f(s, nextIdx);
    return [result + rest, end]
  }
  
  // Otherwise, we may have a word,
  let word = '';
  while (isNaN(s[i]) && s[i] != ']' && i < s.length)
    word = word + s[i++];

  // followed by either the end of an expression
  // or another multiplier
  const [rest, end] = s[i] == ']' ? ['', i + 1] : f(s, i);
  return [word + rest, end];
}

var strs = [
 '2[3[a]b]',
  '10[a]',
  '3[abc]4[ab]c',
  '2[2[a]g2[r]]'
];

for (const s of strs){
  console.log(s);
  console.log(JSON.stringify(f(s)));
  console.log('');
}

Collectives™ on Stack Overflow

Optimal algorithm for this string decompression

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related