Start learning free

LESSON 322 OF 540 · HASH TABLE

Encode and Decode Strings in Go: Length-Prefix 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

    GO · HASH TABLE

    Encode And Decode Strings in Go, explained

    Problem overview

    The task is to turn a slice of strings into one string and back. Encode takes strs and returns a single string. Decode takes that string, and nothing else, and must return the original slice, in the same order. The lesson uses a Codec struct with these two methods, and the tests encode with one Codec value and decode with another, so no state can be shared between the calls.

    The strings can hold any printable character, including #, digits and spaces, and a string can be empty. The list itself can also 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", "", "#"] the encoded string is 3#3#a0#1##.

    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 contains the separator. Joining "a#b" and "c" with # gives a#b#c, and strings.Split returns three pieces, ["a" "b" "c"], instead of two. The statement says any printable character can appear, so no separator is safe.

    The fix is to stop looking for where a string ends and say it up front. Each string is written as its length, a #, and then the string itself. When decoding, you read the digits up to the first #, turn them into a number, and then take exactly that many characters, whatever they are. A # or a digit inside the string is never examined, because the length already says where the string stops. The next piece starts right after it.

    The # after the length is still needed. Without it, a string that starts with a digit would run into its own length: 1 followed by "2x" would look the same as 12 followed by "x". Digits contain no #, so the first # from the current position always marks the end of the length.

    Both methods are linear in N, the total length of all the strings. Encoding appends each string once. Decoding moves an index forward through the encoded string and cuts out each piece once, instead of repeatedly shortening the whole string.

    Step by step

    Encode

    1. Declare a strings.Builder named encoded. A builder collects text in a growing buffer, so appending a piece doesn't copy everything written so far. Joining with += on a plain string would copy the whole result each time and make encoding quadratic.
    2. Loop over strs with range. The index isn't needed, so it goes to _.
    3. Write each piece: strconv.Itoa(len(s)) turns the length into text, followed by "#" and the string itself.
    4. Return encoded.String() after the loop.

    Decode

    1. Create the result as an empty slice of strings, strs := []string{}.
    2. Keep an index i, starting at 0: the position where the next piece begins.
    3. Loop while i < len(s). Each round reads one piece.
    4. Find the #. Start j at i and advance it while s[j] is not '#'. Indexing a Go string gives a byte, so it is compared with a byte literal in single quotes.
    5. Convert the digits. s[i:j] is the length as text, and strconv.Atoi returns the number and an error. The error is skipped with _, because the string came from Encode and always holds valid digits.
    6. Cut out the piece: the characters from j+1 up to j+1+length, appended to strs.
    7. Move i to j + 1 + length, the start of the next piece.
    8. Return strs.

    The solution in Go

    type Codec struct{}

func (this *Codec) Encode(strs []string) string {
    var encoded strings.Builder
    for _, s := range strs {
        encoded.WriteString(strconv.Itoa(len(s)) + "#" + s)
    }
    return encoded.String()
}

func (this *Codec) Decode(s string) []string {
    strs := []string{}
    i := 0
    for i < len(s) {
        j := i
        for s[j] != '#' {
            j++
        }
        length, _ := strconv.Atoi(s[i:j])
        strs = append(strs, s[j+1:j+1+length])
        i = j + 1 + length
    }
    return strs
}

    Go details worth knowing:

    • Lengths are in bytes. len(s) counts bytes and slicing a string cuts by byte offsets, so the two agree with each other. For the lesson's printable ASCII, a byte is a character. For text with other characters it still round-trips, because Encode and Decode both count bytes: len("é") is 2.
    • A for with only a condition is Go's while. Both loops in Decode use that form.
    • s[j] is a byte, not a string. Comparing it with "#" would not compile; '#' is an untyped rune constant that converts to a byte.
    • Slicing a string is cheap. s[a:b] shares the original bytes and copies nothing, which keeps Decode linear.
    • Empty slice versus nil. strs := []string{} gives an empty, non-nil slice, so an empty input decodes to [].

    Complexity

    Time: O(N). Encode writes each string once, and the length prefix adds a few bytes per string. Decode scans each length's digits once and slices each piece once, and i only moves forward.

    Space: O(N) for the encoded string and the decoded slice, which are the outputs.

    Edge cases and common mistakes

    • The empty list and the list with one empty string. [] encodes to "" and decodes to []. [""] encodes to 0# and decodes to a slice with one empty string. The length prefix keeps the two apart.
    • Strings that look like prefixes. ["3#a", "", "#"] encodes to 3#3#a0#1##. Decoding reads 3, then takes three characters, 3#a, and goes on with 0# and 1##.
    • Splitting on #. It breaks on any string that contains the character, as shown above.
    • Forgetting the separator after the length. Without it, the digits of a length and the digits at the start of a string can't be told apart.
    • Cutting s down in each round. Using s = s[j+1+length:] would also work in Go, since slicing doesn't copy, but an index is the version that makes the linear cost obvious.
    • Multi-digit lengths. A string of 12 characters has the prefix 12#. Reading only one digit would break it.

    Testing

    These inputs and the strings Encode produced for them:

    • ["lint", "code", "love", "you"] encodes to 4#lint4#code4#love3#you.
    • ["3#a", "", "#"] encodes to 3#3#a0#1##.
    • [] encodes to the empty string.
    • [""] encodes to 0#.
    • ["", ""] encodes to 0#0#.
    • ["a b", "12#", "x"] encodes to 3#a b3#12#1#x.
    • ["abcdefghijkl"] encodes to 12#abcdefghijkl.

    In every case, Decode returns exactly the original slice.

    Keep going with Go500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free