Encode and Decode Strings

The key idea

Problem

Design an algorithm to encode a list of strings into a single string. The encoded string is then sent over the network and decoded back into the original list of strings.

Machine 1 has a function encode that turns strs (a list of strings) into one combined string. That string travels to Machine 2, whose decode function must reconstruct the exact original list — same strings, same order, same count.

The tricky part is that each string may contain any character, including digits, spaces, or the very symbol you might want to use as a separator. Your scheme must round-trip correctly no matter what bytes appear inside the strings, and it must distinguish an empty list from a list that contains one empty string. You may not assume anything about the contents beyond the stated limits, and you should not rely on any global state shared between the two machines.

Constraints

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] contains any possible characters out of 256 valid ASCII characters.

Examples

Complexity

Time: O(n) Space: O(n)

More Design problems

• Binary Search Tree IteratorMEDIUM
• Design Circular QueueMEDIUM
• Design HashMapEASY
• Design HashSetEASY
• Design TwitterMEDIUM
• Detect SquaresMEDIUM
• Implement Queue using StacksEASY
• Implement Stack using QueuesEASY
• Insert Delete GetRandom O(1)MEDIUM
• LFU CacheHARD
• LRU CacheMEDIUM
• Maximum Frequency StackHARD