Start learning free

LESSON 318 OF 536 · HASH TABLE

Encode and Decode Strings in Python: Length Prefixes

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

    PYTHON · HASH TABLE

    Encode And Decode Strings in Python, explained

    Problem overview

    The class Codec has two methods. encode(strs) takes a list of strings and returns one string that holds all of them. decode(s) takes a string produced by encode and returns the original list, in the same order. The two methods may run in different programs, so decode can use nothing except the string it receives.

    The strings are printable ASCII, so they can contain letters, digits, spaces and punctuation such as #, and any of them can be empty. Both methods must run in time proportional to the total length of all the strings.

    For ["lint", "code", "love", "you"], encode returns '4#lint4#code4#love3#you' and decode turns that back into the same four strings. For ["3#a", "", "#"] the encoded string is '3#3#a0#1##', and decoding it gives the original three strings, including the empty one.

    Approach: write the length first

    The obvious idea is to join the strings with a separator and split on it later. That fails as soon as a separator can appear inside a string. For example, joining ["a,b", "c"] with a comma gives "a,b,c", and splitting on commas returns ['a', 'b', 'c']: three strings instead of two. Any single character you choose can also be part of the data, so a separator can't be trusted.

    The fix is to stop looking for where a string ends and say it up front. Before each string, write its length, then a #, then the string itself. The decoder reads the digits up to the first #, turns them into a number, and then takes exactly that many characters. It never looks at what those characters are, so a # or a digit inside a string is harmless.

    The # after the length is still needed. It marks where the digits end. Without it, "3" followed by the string "1ab" would produce 31ab, and the decoder couldn't tell whether the length is 3, 31 or something else. The first # after a piece's start is always the one encode wrote, because a length is made of digits only.

    An empty list encodes to the empty string, which decodes to an empty list. A list holding one empty string encodes to '0#', so the two cases stay different.

    Step by step

    Encoding

    1. Create an empty list parts. It collects one piece per string. Joining the pieces once at the end is linear, while adding each piece onto one growing string can copy that string again each time.
    2. Loop over the strings.
    3. Build each piece as str(len(s)) + "#" + s. The length must be converted to text with str before it can be joined to other strings with +. Add the piece to parts.
    4. Return "".join(parts), which glues the pieces together with nothing between them.

    Decoding

    1. Create an empty result list named strs.
    2. Keep an index i, starting at 0, for the position where the next piece begins.
    3. Loop while i < len(s). Each round reads one whole piece: a length, a #, then that many characters.
    4. Find the #. Start j at i and move it forward while s[j] isn't "#".
    5. Read the length. The slice s[i:j] holds the digits, and int turns them into a number.
    6. Take the string: the length characters starting right after the #, which is the slice s[j + 1:j + 1 + length]. Add it to the result.
    7. Move i to j + 1 + length, the start of the next piece.
    8. Return the result. An empty s never enters the loop and gives an empty list.

    The solution in Python

    class Codec:
    def encode(self, strs: List[str]) -> str:
        parts = []
        for s in strs:
            parts.append(str(len(s)) + "#" + s)
        return "".join(parts)

    def decode(self, s: str) -> List[str]:
        strs = []
        i = 0
        while i < len(s):
            j = i
            while s[j] != "#":
                j += 1
            length = int(s[i:j])
            strs.append(s[j + 1:j + 1 + length])
            i = j + 1 + length
        return strs

    A few Python details matter here. Strings are immutable, so a + b always builds a new string. That is why encode collects pieces in a list and calls "".join once. A slice such as s[j + 1:j + 1 + length] includes the start index and excludes the end index, so it holds exactly length characters. When length is 0 the slice is empty, which is how an empty string comes back. Slicing also never raises an error for bounds that run past the end, but with strings made by encode that never happens.

    Complexity

    encode visits each string once. Computing len(s) is constant time, and building a piece and joining the pieces copy each character a constant number of times, so the time is O(N), where N is the total length of all the strings. (The pieces also carry the length digits and the #, which add a little per string and don't change the order.) The extra space is O(N) for the pieces and the output.

    decode moves the pointers j and i only forward. The inner loop scans the digits of one length, and each slice copies one string. Every character of s is passed over a constant number of times, so the time is O(N). The result list takes O(N) space.

    Moving an index through s is what keeps this linear. Repeatedly cutting the front off the string, with something like s = s[j + 1 + length:], copies the rest of the string every time, and that adds up to quadratic time on long inputs.

    Edge cases and common mistakes

    • An empty list versus a list with one empty string. [] encodes to '' and [""] encodes to '0#'. Decoding gives back [] and [''].
    • Strings that look like pieces. ["12#ab", "5"] encodes to '5#12#ab1#5'. The decoder reads 5, takes 12#ab as one string, then reads 1 and takes 5. Because it counts characters, the content is never parsed.
    • Lengths with several digits. A string of 150 characters has the prefix 150#. This is why the decoder scans up to the # instead of reading a single digit.
    • Forgetting str(). len(s) + "#" raises a TypeError, because an integer can't be added to a string.
    • Off-by-one in the slice. The string starts at j + 1, just after the #, not at j.

    Testing

    Try these lists, encoding each and decoding the result. The decoded list should equal the input every time.

    strsencode(strs)
    ["lint", "code", "love", "you"]'4#lint4#code4#love3#you'
    ["3#a", "", "#"]'3#3#a0#1##'
    []''
    [""]'0#'
    ["", "", ""]'0#0#0#'
    ["12#ab", "5"]'5#12#ab1#5'
    Keep going with Python500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free