Design a class with two methods. encode takes a list of strings and returns one string. decode takes a string that encode returned and gives back the list: the same strings, in the same order. The format of that one string is yours to design; nothing is checked about it except that it works. Each test gives a list to encode on one object, then gives the string that came back to decode on a second object, loaded separately: nothing you keep on the object or on the class is there for decode to read, so the string has to carry the whole list. A string in the list may be empty and may contain any character at all, including whichever one you were about to use as a separator.
Examples
Example 1:
Input: strs = ["rain","snow"]
Output: ["rain","snow"]
Explanation: decode(encode(strs)) gives the list back. What encode returned in between is not checked.
Example 2:
Input: strs = [""]
Output: [""]
Explanation: one empty string, which is not the same as no strings.
Example 3:
Input: strs = []
Output: []
Example 4:
Input: strs = ["wind, rain","sun,",","]
Output: ["wind, rain","sun,",","]
Explanation: a comma is a character like any other, so it cannot mark where one string ends and the next begins.
Constraints
0 <= strs.length < 100
0 <= strs[i].length < 200
strs[i] may contain any of the 256 ASCII characters, not only letters and digits.
encode and decode are called on two different objects.
Prerequisites
Serialization — turning a structure into a flat sequence and back, and choosing a format that survives ambiguity.
How to think about it
1. Write the Length, Then the String Optimal
Intuition
A separator alone cannot work. Whatever character you pick, a string may contain it, and joining cannot tell an empty list from a list holding one empty string. So say how long each string is before writing it: encode writes the length, a '#', then the string; decode reads the digits up to the next '#', takes exactly that many characters whatever they are, and goes round again. The '#' only ends the number. It is never searched for inside a string, because the length has already said where the string stops.
Algorithm
1. encode: for each string, append its length, a '#', and the string. No strings at all is the empty string. 2. decode: start a cursor at zero. 3. Find the next '#' from the cursor; the digits before it are a length. 4. Take exactly that many characters after the '#' as one string, and move the cursor past them. 5. Repeat until the cursor reaches the end.
Time & Space
Time O(n) for encode and O(n) for decode, where n is the total number of characters. Space O(n) for what each returns.