Problem overview
The class Codec has two methods. encode(strs) turns an array of strings into a single string, and decode(s) turns that string back into the original array, in the same order. The two methods run on different Codec objects, as if the string had travelled to another machine, so decode may use only the string it receives and nothing remembered by encode.
The strings may hold any printable character, including #, digits and spaces, and a string may be empty. For ["lint","code","love","you"] one valid encoding is "4#lint4#code4#love3#you". For ["3#a","","#"] the encoding is "3#3#a0#1##", and decoding it gives the same three strings back. Both methods must take time proportional to the total length of the strings.
Approach: write each length before its string
The obvious idea is to join the strings with a separator and split on it later. It fails as soon as a string can contain the separator. With "#" as the separator, ["a#b", "c"] becomes "a#b#c", and splitting it gives ['a', 'b', 'c']: three strings instead of two. Because every printable character may appear inside a string, no single character can be a safe separator.
The fix is to stop looking for the end of a string and to say where it ends instead. Before each string, write its length, then a #, then the string itself: <length>#<string>. To decode, read the digits up to the next #, then take exactly that many characters, whatever they are. The next piece starts right after them. The decoder never looks inside a string, so a # or a digit in the content can't confuse it.
The # after the length is still needed. It marks where the digits end, so a string that starts with a digit doesn't run into its own length: 12 followed by 345 would be ambiguous without it. A length is made only of digits, so the first # after the start of a piece is always the one encode wrote.
The empty list and the list holding one empty string stay different: [] encodes to "", while [""] encodes to "0#".
Step by step
encode
- Start with an empty string. Declare
encodedwithlet, since it grows. - Loop over the strings with
for...of, taking each one ass. - Append a piece for each string: its length, a
"#", then the string. Adding a number to a string with+turns the number into its digits, sos.length + "#"is text such as"5#". - Return
encodedafter the loop.
decode
- Prepare the result: a constant
strsof typestring[], empty at first. - Keep an index
i, starting at 0, for the place where the next piece begins. - Loop while
i < s.length. Each round reads one piece. - Find the
#. Startjatiand move it forward whiles[j]isn't"#". - Read the length.
s.substring(i, j)holds the digits, andNumberconverts them. - Take the string: exactly
lengthcharacters starting right after the#, that is,substring(j + 1, j + 1 + length). The end index is exclusive. Push it ontostrs. - Move
itoj + 1 + length, where the next piece begins. - Return
strs.
The solution in TypeScript
class Codec {
encode(strs: string[]): string {
let encoded = "";
for (const s of strs) {
encoded += s.length + "#" + s;
}
return encoded;
}
decode(s: string): string[] {
const strs: string[] = [];
let i = 0;
while (i < s.length) {
let j = i;
while (s[j] !== "#") {
j++;
}
const length = Number(s.substring(i, j));
strs.push(s.substring(j + 1, j + 1 + length));
i = j + 1 + length;
}
return strs;
}
}
Some details worth knowing:
- Number plus string. In
s.length + "#" + s, the first+has a number on the left and a string on the right, so it concatenates:5 + "#"is"5#". The whole expression has typestring, which matchesencoded. - Indexing a string.
s[j]is a one-character string, so comparing it with"#"using!==is a plain text comparison. Indexing past the end givesundefined, not an error. The loop never gets there on valid input, because every length is followed by a#. - substring.
substring(start, end)takes the characters fromstartup to, but not including,end. Passing the same number twice gives an empty string, which is how an empty entry such as"0#"decodes. - Types are only notes.
string[]and: stringare erased when the code is compiled to JavaScript. They help the compiler check your code, and they don't validate the string thatdecodereceives.
Complexity
Time: O(N), where N is the total length of all the strings. encode adds each string once, and the loop does a constant amount of work around each one. In decode, the inner loop moves j over the digits of a length, and substring copies the characters of one string. Each character of s is passed over a constant number of times, and i only moves forward. Cutting s into shorter and shorter copies in every round would copy the rest of the string each time and slow decoding down, which is why the code moves an index instead.
Space: O(N) for the encoded string and for the decoded array, apart from the input itself. Beyond that, decode uses a few integers.
Edge cases and common mistakes
- Empty list.
encode([])returns"", anddecode("")never enters the loop, so it returns[]. - Empty strings.
[""]encodes to"0#"and decodes to one empty string.["", ""]encodes to"0#0#"and decodes to two. - A
#or digits inside a string.["3#a","","#"]works because the decoder trusts the length: it reads 3, then takes3#aas three characters. - Forgetting the
#after the length. Without it, the digits of a length and the digits at the start of a string blur together. - Using a fixed-width length. A one-digit length would break for long strings. The
#allows a length of any number of digits. - Off-by-one in the slice. The string starts at
j + 1, just after the#, not atj. - Counting the wrong thing. The length is the number of characters in the string, not including the prefix.
Testing
["lint","code","love","you"]encodes to"4#lint4#code4#love3#you"and decodes back to the same array.["3#a","","#"]encodes to"3#3#a0#1##"and decodes back to the same array.[]encodes to""and decodes to[].[""]encodes to"0#"and decodes to[""].["a b", "12", "#3#"]encodes to"3#a b2#123##3#"and decodes back to the same array.
