CODEWITHSUNDEEP
algorithmdata-structures
village_pleb
village_pleb

Reputation: 28

N Stage string compression : Algorithm for decompression

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?

Upvotes: 1

Views: 64

Answers (1)

Surt
Surt

Reputation: 16119

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 ...

Upvotes: 2

Related Questions