Encode and Decode Strings

Problem

Design two functions. encode takes a list of strings and produces a single string. decode takes that single string and reproduces the original list exactly. The strings may contain any character, including whatever characters you might be tempted to use as separators, and the list may contain empty strings. The encoded form is the only thing passed from encode to decode; no other state is shared.

• The list holds at most 1,000 strings and may be empty.
• Any single string is at most 500 characters long and may be empty.
• Strings may contain any character at all, including #, digits, newlines, and NUL, so no character is reserved.

Examples

• ["sun", "moon"] → encode → "3#sun4#moon" with the scheme below → decode → ["sun", "moon"].
• ["k;v", "7#x", ""] → round-trips to ["k;v", "7#x", ""]; the ; and the 7# inside the strings must not be mistaken for framing.
• ["", ""] → round-trips to ["", ""]; two empty strings are distinct from one empty string or an empty list.

Hints

1. Any single separator character can also appear inside a string, so it cannot mark boundaries by itself.
2. If the decoder knew how long the next string was, it would not need a separator at all.
3. Prefix each string with its length and a terminator such as #; the decoder reads the number, then reads exactly that many characters.