Pack a Word List Into One String
Problem
Write pack(words), which turns a list of strings into one string, and unpack(text), which turns that string back into the original list. Each word is written as its length in decimal, then a #, then the word itself. Words can be empty and can contain any character, including digits and #, so unpack must never search for a separator inside a word.
Examples
Input: words = ["hi", "#1"]
Output: pack -> "2#hi2##1"
unpack -> ["hi", "#1"]
Why: after reading "2#", the next two characters are taken whole, "#" or notInput: words = ["", "a"]
Output: pack -> "0#1#a"
Why: an empty word still gets its length, so it survives the round tripInput: words = []
Output: pack -> ""
unpack -> []
Why: edge case, nothing to write and nothing to readHints
0 / 3
Joining with a separator breaks as soon as a word contains that separator. The length in front of each word is what removes the ambiguity.
The first # after a length is always the end of that length, because a length is only digits. Everything after it is counted, not searched.
Keep a read position. Scan digits up to the next #, turn them into a number n, take exactly the n characters after the #, and move the read position past them. Repeat until the position reaches the end.
Solution
The length prefix tells the reader exactly how many characters to take, so the contents of a word never matter. Reading a length is safe because a length is only digits, which makes the first # after it the true end of the number. Each character is visited a constant number of times while packing and while unpacking. Time is O(L) for L total characters, and space is O(L) for the output.
def pack(words):
return "".join(f"{len(w)}#{w}" for w in words)
def unpack(text):
words, i = [], 0
while i < len(text):
hash_at = text.index("#", i) # end of the length digits
n = int(text[i:hash_at])
words.append(text[hash_at + 1:hash_at + 1 + n])
i = hash_at + 1 + n # jump over the word, never into it
return words
print(pack(["hi", "#1"])) # -> 2#hi2##1
print(unpack("2#hi2##1")) # -> ['hi', '#1']
print(unpack(pack(["", "a"]))) # -> ['', 'a']
print(unpack(pack([]))) # -> []Stuck on the idea rather than the code? Encode and Decode Strings covers it.