Start learning free

LESSON 322 OF 540 · HASH TABLE

Encode and Decode Strings in Scala: Length-Prefix Encoding in O(N)

Practice O(n) Read the full explanation

Design a way to turn a list of strings into one string and back. One program encodes the list and sends the string to another program, which decodes it into the same list of strings, in the same order.

Implement the class Codec:

  • encode(strs) gets a list of strings strs and returns one string that holds all of them.
  • decode(s) gets a string s made by encode and returns the original list of strings.

The strings can contain any printable character, including #, digits and spaces, and a string can be empty. So no single character can mark where one string ends and the next begins: that character could be inside a string too.

Each test is one list. It is encoded with one Codec object and decoded with another, as if the string were sent to another machine, so decode can use only the string it gets. The output is the decoded list. The starter code spells the method names the way your language does.

 

Example 1:

Input: strs = ["lint","code","love","you"]
Output: ["lint","code","love","you"]
Explanation: encode can return "4#lint4#code4#love3#you": for each string, its length,
a #, then the string itself. decode reads the 4 before the first #, takes the 4 characters
after it, "lint", and goes on from there.

Example 2:

Input: strs = ["3#a","","#"]
Output: ["3#a","","#"]
Explanation: The encoded string is "3#3#a0#1##". decode reads the length 3 up to the first #,
then takes exactly 3 characters, "3#a", although they hold a digit and a #.
Then "0#" gives the empty string, and "1##" gives "#".

Example 3:

Input: strs = []
Output: []
Explanation: An empty list encodes to the empty string "", which decodes to no strings at all.
A list with one empty string, [""], encodes to "0#" instead, so the two stay different.

 

Constraints:

  • 0 <= strs.length <= 105
  • 0 <= strs[i].length <= 200
  • The total length of all the strings is at most 106.
  • strs[i] consists of printable ASCII characters (codes 32 to 126): letters, digits, spaces and punctuation such as #.

Note:

Both encode and decode should run in O(N) time, where N is the total length of all the strings.

Write each string's length in front of it, followed by a #: <length>#<string>. To decode, read the digits up to the next #, then take exactly that many characters, whatever they are; the next string starts right after them.

Keep both methods linear: don't copy the whole encoded string again for every string you add, and don't cut s into shorter and shorter copies while decoding; move an index through it instead.

STEP 1 OF 14
    Ctrl + Enter to check

    SCALA · HASH TABLE

    Encode And Decode Strings in Scala, explained

    Problem overview

    The class Codec has two methods. encode(strs: List[String]) packs a list of strings into one String. decode(s: String) takes that string, made by a different Codec object, and returns the original List[String], in the same order. Strings can hold any printable character, including #, digits and spaces, and they can be empty.

    For ["lint","code","love","you"], encode returns 4#lint4#code4#love3#you, and decode turns it back into the same four strings. For ["3#a","","#"], the encoded string is 3#3#a0#1##, and it still decodes to the three original strings. An empty list encodes to "", while a list holding one empty string, [""], encodes to 0#, so the two stay different.

    Approach: say how long each string is

    The obvious idea is to join the strings with a separator, such as #. It breaks as soon as a string contains the separator. Joining "a#b" and "c" gives a#b#c, and splitting on # returns three pieces instead of two. Any single separator character can appear inside a string, so no choice of character is safe.

    The fix is to stop searching for a boundary and write down the length instead. In front of each string, put its length and a #: <length>#<string>. To decode, read the digits up to the next #, then take exactly that many characters, whatever they are, and the next piece starts right after them. The decoder never looks inside a string, so a # or a digit in the data can't confuse it.

    The # after the length is still needed. Without it, the strings "1a" and "b" would encode as 21a1b, and the decoder couldn't tell where the digits of one length end and the string begins. The # is only read while scanning the digits, and a length is made of digits only, so the first # after the start of a piece is always the one encode wrote.

    Both methods should run in O(N) time, where N is the total length of all the strings. That shapes two choices: build the output with a StringBuilder instead of repeated +, and walk through the encoded string with an index instead of cutting it into shorter copies.

    Step by step

    encode

    1. Create a StringBuilder named encoded. It appends to a growing buffer, so adding a piece doesn't copy everything written so far.
    2. Loop over the strings with for (s <- strs).
    3. Append the three parts of each piece: the length, the '#' and the string itself. Each append returns the builder, so the calls chain on one line.
    4. Return encoded.toString. It is the last expression of the method, so it is the result.

    decode

    1. Create an ArrayBuffer[String] named strs to collect the strings as they are read.
    2. Keep an index i in a var, starting at 0. It marks where the next piece begins.
    3. Loop while i < s.length. Each round reads one piece. An empty s never enters the loop, which is why an empty list comes back as an empty list.
    4. Find the #: start j at i and move it forward while s(j) is not '#'.
    5. Read the length: s.substring(i, j) holds the digits, and toInt turns them into a number.
    6. Take the string: exactly length characters starting at j + 1, added to strs with +=.
    7. Move i to j + 1 + length, where the next piece starts.
    8. Return strs.toList, the buffer converted to the List the method promises.

    The solution in Scala

    class Codec {
    def encode(strs: List[String]): String = {
        val encoded = new StringBuilder()
        for (s <- strs) {
            encoded.append(s.length).append('#').append(s)
        }
        encoded.toString
    }

    def decode(s: String): List[String] = {
        val strs = scala.collection.mutable.ArrayBuffer[String]()
        var i = 0
        while (i < s.length) {
            var j = i
            while (s(j) != '#') {
                j += 1
            }
            val length = s.substring(i, j).toInt
            strs += s.substring(j + 1, j + 1 + length)
            i = j + 1 + length
        }
        strs.toList
    }
}

    The Scala details worth noticing:

    • StringBuilder.append accepts many types. append(s.length) takes an Int, append('#') a Char and append(s) a String. Each call writes the text form of its argument, so append(12) adds the characters 1 and 2.
    • Single quotes are a Char, double quotes a String. s(j) != '#' compares a character with a character. Scala reads a character with parentheses, s(j), not square brackets.
    • substring(start, end) stops before end. s.substring(i, j) is the digits from i up to, but not including, the # at j. The string itself is s.substring(j + 1, j + 1 + length), and when length is 0 that is an empty string.
    • toInt parses a decimal string. It turns "12" into 12. It throws NumberFormatException on anything else, which can't happen here because the digits come from encode.
    • val versus var. encoded, strs and length never get reassigned, so they are val. The buffers still change, because val fixes the reference, not the contents. i and j move, so they are var.
    • Mutable buffer, immutable result. ArrayBuffer grows with +=; toList copies it into an immutable List, which is what decode returns.

    Complexity

    Time: O(N) for both methods, where N is the total length of the strings. encode appends each character once, plus a few digits for each length. decode moves j over the digits of each length and then jumps i past the string in one step. Every character of s is passed over once, and each substring copies only the characters it returns.

    Space: O(N) for the encoded string and the decoded list, which are the outputs. Beyond them, only a few integers are kept.

    Edge cases and common mistakes

    • Empty list and list with an empty string. List() encodes to "" and decodes to List(). List("") encodes to 0# and decodes to a list holding one empty string. The length prefix keeps them apart.
    • A string made of separators or digits. List("12#", "a b", "0") encodes to 3#12#3#a b1#0 and decodes correctly, because the decoder only trusts the length.
    • Several digits in a length. A string of 200 characters has the length prefix 200#. Reading only one digit would break such strings, which is why the decoder scans up to the #.
    • Forgetting the #. Prefixing the length alone makes "1a" followed by "b" ambiguous.
    • Using split. Splitting on # fails on any string that contains one.
    • Building with + in a loop. result = result + piece copies the whole result each time, which makes encode slower than linear with 100,000 strings.
    • Cutting s shorter while decoding. Taking s = s.substring(...) after every piece copies the rest of the string each time. Moving an index avoids it.

    Testing

    • List("lint", "code", "love", "you") encodes to 4#lint4#code4#love3#you and decodes back to the same list.
    • List("3#a", "", "#") encodes to 3#3#a0#1## and decodes back to the same list.
    • List() encodes to "" and decodes to List().
    • List("") encodes to 0# and decodes to List("").
    • List("", "") encodes to 0#0# and decodes to List("", "").
    • A list of 100,000 copies of "abcdefghij" decodes back to an equal list.
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free