Encode and Decode Strings
Encode and Decode Strings is a medium Arrays & Hashing problem from the Blind 75. The key pattern is length-prefix framing, and a good solution runs in O(total length) time.
Problem
Round-trip a list of arbitrary UTF-8 strings using one unambiguous encoded string. Print the decoded list.
Examples
Example 1
Input
["north","","a:b","雪"]Output
["north","","a:b","雪"]Example 2
Input
["hello","world"]Output
["hello","world"]Example 3
Input
[""]Output
[""]Approach
Write each string as its length, a separator and the raw text. Decoding reads digits up to the separator, then takes exactly that many characters, so any content is safe.
| Pattern | Length-prefix framing |
|---|---|
| Time | O(total length) |
| Space | O(total length) |
Watch out for
Count length in the same unit you slice by; multi-byte characters and strings containing the separator must survive the round trip.