Problem overview
The class Codec has two methods. encode receives a List<String> and returns a single String. decode receives that string, on what the tests treat as a different machine with a different Codec object, and must return the original list in the same order. Nothing is shared between the two calls except the string itself.
The strings can hold any printable character, including digits, spaces and #, and they can be empty. For ["lint", "code", "love", "you"] the encoded string is 4#lint4#code4#love3#you, and decoding it gives the same four strings back. For ["3#a", "", "#"] it is 3#3#a0#1##, and decoding gives the same three strings again. An empty list encodes to the empty string, and [""] encodes to 0#, so those two inputs stay apart.
Approach: say how long each string is
The obvious idea is to join the strings with a separator such as , or # and split on it when decoding. It fails because any separator character can also appear inside a string, and then decode cuts in the wrong place. Escaping the separator inside the strings works, but it makes both methods more complicated.
A length prefix avoids the problem. Before each string, write how many characters it has, then a #, then the string itself. When decoding, read the digits up to the first #, convert them to a number length, and take exactly length characters after the #. Those characters are never inspected, so they may contain anything. The next piece starts right after them.
The # after the length is still needed. Without it, 12 followed by a string that starts with a digit could be read as a longer length. Because a length is only digits, the first # reached while reading a length is always the one that encode wrote.
Both methods should be linear in N, the total length of the strings. Two habits keep them that way: build the output with a StringBuilder instead of adding to a String in a loop, and walk through the encoded string with an index instead of cutting it into shorter and shorter copies.
Step by step
encode
- Create a
StringBuildernamedencoded. Appending to it adds text to the end of one growing buffer. Using+=on aStringwould build a brand new string each time, and the repeated copying adds up. - Loop over the strings with
for (s in strs). - Append the three pieces for each string:
s.length, the character'#'ands.appendreturns the builder itself, so the calls chain on one line. - Return
encoded.toString()after the loop. With an empty list the loop never runs and the result is the empty string.
decode
- Create the result list
strs, an emptyArrayList<String>(), and an indexiset to 0. The index marks where the next piece starts. - Loop while
i < s.length. Each round of the loop reads exactly one piece. An empty input skips the loop and gives an empty list. - Find the
#. Startjatiand add 1 to it whiles[j]is not'#'. The characters fromiup tojare the length's digits. - Convert the digits with
s.substring(i, j).toInt()and store the number inlength. - Take the string with
s.substring(j + 1, j + 1 + length)and add it tostrs. The end index is exclusive, so this takes exactlylengthcharacters. - Move
itoj + 1 + length, where the next length begins, and returnstrsafter the loop.
The solution in Kotlin
class Codec {
fun encode(strs: List<String>): String {
val encoded = StringBuilder()
for (s in strs) {
encoded.append(s.length).append('#').append(s)
}
return encoded.toString()
}
fun decode(s: String): List<String> {
val strs = ArrayList<String>()
var i = 0
while (i < s.length) {
var j = i
while (s[j] != '#') {
j += 1
}
val length = s.substring(i, j).toInt()
strs.add(s.substring(j + 1, j + 1 + length))
i = j + 1 + length
}
return strs
}
}
The Kotlin details worth a closer look:
appendaccepts several types.StringBuilder.append(Int)writes the decimal digits, soappend(s.length)adds4for a four-character string.append('#')takes aCharandappend(s)takes aString.- Characters and strings differ.
s[j]is aChar, so it is compared with'#'in single quotes. Comparing it with the string"#"would not compile. substring(start, end)includesstartand excludesend. Whenlengthis 0,j + 1andj + 1 + lengthare equal, and the result is the empty string, which is how an empty element survives the round trip.toInt()parses the digits. It would throw aNumberFormatExceptionif it got anything else, butdecodeonly receives whatencodemade.varandval.iandjchange, so they arevar.lengthis set once per round, so it isval.
Complexity
Time: O(N) for both methods. encode appends each string once, and the builder copies each character into its buffer a constant number of times on average. decode moves i forward past every character once. Scanning for # reads only the digits of the length, and substring copies each string once.
Space: O(N). The encoded string and the decoded list each hold about N characters, plus a few characters of length prefix per string.
Edge cases and common mistakes
- Strings that look like the format.
["3#a", "", "#"]round-trips correctly, because decode trusts the length and never looks at what is inside the string. - Empty list versus a list with one empty string.
[]encodes to""and[""]encodes to"0#", so decode returns two different results. - Several empty strings.
["", ""]encodes to0#0#and decodes to two empty strings. - Multi-digit lengths. A string of 12 characters gets the prefix
12#. Reading only one digit, or assuming one-digit lengths, breaks as soon as a string reaches 10 characters. - Leaving out the
#. Without it, the length of the next string could run into the digits that start the previous string. - Cutting
sin pieces. Replacingsbys.substring(...)in each round copies the remaining text every time, which can turnO(N)intoO(N * k)forkstrings.
Testing
["lint", "code", "love", "you"]encodes to4#lint4#code4#love3#youand decodes back to the same list.["3#a", "", "#"]encodes to3#3#a0#1##and decodes back to the same list.[]encodes to the empty string and decodes to[].[""]encodes to0#and decodes to[""].["", ""]encodes to0#0#and decodes to["", ""].["a b", "12", "#5#"]encodes to3#a b2#123##5#and decodes back to the same list.
