Encode and Decode Strings
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Turn a list of strings into one string and back again, even if the strings contain any character.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1If you join with a comma, what breaks?
- Hint 2How could the decoder know exactly how many characters to read for the next word?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A courier packs several parcels into one big box. A comma between parcels would not work because a parcel's content can contain commas. So every parcel gets a label on top first: "5 letters inside". The receiver reads the label, then takes exactly that many letters, then reads the next label.
- The obvious way
Join with a special separator: fails if the data contains it.
- The key insight
Write each word as its length, then a # sign, then the word itself, for example "4#lint". To decode, read the digits up to the first #, which gives the length, then take exactly that many characters. The content of a word is never inspected, so any character is safe, even another #.
- The algorithm
- Encode: for every word write (its length) + "#" + (the word), and join them all.
- Decode: stand at the start. Find the next "#"; the number before it is the length.
- Take exactly that many characters after the "#": that is one word.
- Jump past the word and repeat until the text ends.
Watch it run
Examplewords = ["lint", "co#de"]
Encode: "lint" has 4 letters -> 4#lint. "co#de" has 5 letters -> 5#co#de.
4#lint5#co#de
Where people slip
- Search for the # starting at the current position and take only the FIRST one: the word itself may contain more.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def encode(words):
return "".join(f"{len(word)}#{word}" for word in words)
def decode(text):
words = []
start = 0
while start < len(text):
hash_at = text.index("#", start) # the first # after the length digits
length = int(text[start:hash_at])
words.append(text[hash_at + 1 : hash_at + 1 + length])
start = hash_at + 1 + length
return wordsNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.