Encode and Decode Strings
MediumArrays and hashing
Write two functions. encode(strs) turns a list of strings into one string, and decode(s) turns that string back into the original list.
Each test calls encode on a list, passes what it returns to decode, and expects the very same list back, in the same order. The strings can hold any character, including digits, #, commas and spaces; a string can be empty, and so can the list. decode must rebuild the list from the string alone; keep nothing between the two calls.
Examples
Input: strs = ["red", "green", "blue"] Output: ["red", "green", "blue"]
The list is encoded into one string, and decoding it gives the three words back.
Input: strs = ["2#ab", "", "x,y"] Output: ["2#ab", "", "x,y"]
Digits, # and commas can be part of a string, and a string can be empty.
Constraints
0 ≤ strs.length ≤ 2000 ≤ strs[i].length ≤ 200- Strings can contain any of the 256 ASCII characters.
Stuck?
Hint 1
Any separator you choose can also appear inside a string, so a separator alone cannot tell you where one string ends.
Hint 2
Write each string’s length in front of it, followed by a marker: 5#hello. To decode, read the digits up to the marker, then take exactly that many characters, whatever they are.
The idea
No separator is safe on its own, because any character can appear inside a string. Write each string's length in front of it instead. The decoder reads the length first and then takes exactly that many characters, so nothing inside a string, # included, is mistaken for a boundary.
Time O(n) for n characters in allExtra space O(n)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
Each string becomes its length, a #, then the string itself. The # marks where the digits end, since a length can have more than one digit. An empty list encodes to the empty string.
function encode(strs) { return strs.map((s) => s.length + '#' + s).join('');} function decode(s) { const out = []; let i = 0; while (i < s.length) { const mark = s.indexOf('#', i); const length = Number(s.slice(i, mark)); out.push(s.slice(mark + 1, mark + 1 + length)); i = mark + 1 + length; } return out;}The trap
Joining the strings with # and splitting on # works for plain words. It breaks when a string holds a # of its own, which split reads as a boundary. It also cannot tell an empty list from a list of one empty string, since both encode to the same empty text.
function encode(strs) { return strs.join('#'); // breaks when a string holds a #} function decode(s) { return s.split('#');}