N Stage string compression : Algorithm for decompression

Question

You have a key-value pair given:

"Adsddf" : ?

"ds?xsc" : :

"csdcs:" : #

...n items.

The goal is to decompress a string : Example : String: "ac3d:cs?" will translate to : ac3ddsAdsddfxsccsAdsddf

Basically in place substitution for every character.

What is the best algorithm to achieve this?

Nimantha · Accepted Answer · 2021-11-12 13:05:37Z

2

Best is somewhat nebulous, but here is a possible solution.

Pseudo code

# reverse lookup
rev = {}
for key, value in items
  rev[value] =  key

result = ""

decode(input)
  for letter in input
    if letter in rev
      decode(rev[letter])
    else
      result.append(letter)

Just be careful that there are no cycles ...

edited Nov 12, 2021 at 13:05

Nimantha

6,5376 gold badges32 silver badges78 bronze badges

answered Aug 18, 2021 at 12:52

Surt

16.2k3 gold badges27 silver badges40 bronze badges

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

2 Comments

Sneftel Over a year ago

Missing an else there, but yeah. This is the cleanest approach, and that’s a good default assumption for ‘best’ (particularly since any sane algorithm will have the same time complexity).

Surt Over a year ago

@Sneftel oh yes, I missed that.

Collectives™ on Stack Overflow

N Stage string compression : Algorithm for decompression

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related