Start learning free

LESSON 325 OF 543 · HASH TABLE

Encode and Decode Strings in Rust: 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 15
    Ctrl + Enter to check

    RUST · HASH TABLE

    Encode And Decode Strings in Rust, explained

    Problem overview

    The Codec struct has two methods. encode takes a Vec<String> and returns a single String. decode takes a string made by encode and returns the original vector, with the same strings in the same order. The two calls happen on different Codec objects, so decode can rely on nothing but the string it receives.

    The strings can hold any printable ASCII character, including digits, spaces and #, and a string can be empty. For ["lint", "code", "love", "you"], one valid encoding is "4#lint4#code4#love3#you", and decoding it gives the four words back. An empty vector must come back as an empty vector, and [""] must come back as a vector holding one empty string.

    Approach: write each length first

    The obvious idea is to put a separator between the strings, but any character you pick can also appear inside a string. With # as the separator, ["a#b"] and ["a", "b"] would both become a#b, and nothing could tell them apart.

    The fix is to stop searching for the end of a string and say where it ends instead. Before each string, write its length and a #. The decoder reads the digits up to the first #, converts them to a number, and takes exactly that many characters, whatever they are. It never looks inside the string, so a # or a digit in the middle can't confuse it.

    The # after the length has a job too: without it, a string that starts with a digit would run into its own length. "3" followed by "12" must not be readable as "31" followed by "2". Because the digits come first and the # ends them, the first # after a piece starts is always the one encode wrote.

    The trickiest input is ["3#a", "", "#"]. It encodes to "3#3#a0#1##". Decoding goes like this:

    start ifirst # at jlengthpiece takennext i
    013"3#a"5
    560""7
    781"#"10

    The first piece holds a digit and a #, and it is still taken whole, because the decoder counted three characters instead of looking for a marker. At i = 10 the string is used up and the loop ends.

    Both methods should take time proportional to the total length of the strings, N. That rules out two tempting shortcuts: copying the whole encoded string again for every string you add, and cutting the input into shorter and shorter copies while decoding. The solution appends to one String and moves an index through the input.

    Step by step

    encode

    1. Create the result. encoded is a let mut empty String that every piece will be appended to.
    2. Loop over &strs. Borrowing the vector means the strings stay where they are instead of being moved out of it.
    3. Append one piece per string. format! fills its {} placeholders in order: the length, a #, then the string. push_str takes a &str, so the piece is passed with &.
    4. Return encoded with no semicolon, so it is the function's value.

    decode

    1. Take the bytes. s.as_bytes() gives a &[u8], where any position is read in one step.
    2. Create the result and the index. strs starts as an empty Vec<String>, and i, the start of the next piece, starts at 0.
    3. Loop while i < bytes.len(). Each round reads one piece. An empty input never enters the loop.
    4. Find the #. Start j at i and move it forward until bytes[j] is b'#', the byte value of the character #. The bytes between i and j are the digits of the length.
    5. Parse the length. s[i..j].parse().unwrap() needs the annotation length: usize, because parse can produce many kinds of numbers and must be told which one.
    6. Take the string. The length bytes after the # run from j + 1 up to, but not including, j + 1 + length. to_string() copies that slice into an owned String for the vector.
    7. Move the index to j + 1 + length, where the next piece starts.
    8. Return strs.

    The solution in Rust

    struct Codec {}

impl Codec {
    fn new() -> Self {
        Codec {}
    }

    fn encode(&self, strs: Vec<String>) -> String {
        let mut encoded = String::new();
        for s in &strs {
            encoded.push_str(&format!("{}#{}", s.len(), s));
        }
        encoded
    }

    fn decode(&self, s: String) -> Vec<String> {
        let bytes = s.as_bytes();
        let mut strs: Vec<String> = Vec::new();
        let mut i = 0;
        while i < bytes.len() {
            let mut j = i;
            while bytes[j] != b'#' {
                j += 1;
            }
            let length: usize = s[i..j].parse().unwrap();
            strs.push(s[j + 1..j + 1 + length].to_string());
            i = j + 1 + length;
        }
        strs
    }
}

    Rust details worth knowing:

    • len() counts bytes. For printable ASCII, one character is one byte, so the length written by encode and the length used by decode agree. "é".len() is 2, and the slicing in decode also works in bytes. That is fine here, because the lesson only uses ASCII.
    • Slices of a String use byte positions. s[i..j] panics if either end falls inside a multi-byte character. With ASCII input every position is a boundary, so this never happens.
    • b'#' is a u8. Iterating over bytes means comparing with a byte literal, not with the char '#'.
    • unwrap panics on bad input. decode trusts that its argument came from encode. A string such as "x#" would panic at parse, and a string with no # would run j past the end of bytes. For this lesson that is acceptable; a real protocol would return an error instead.
    • The temporary from format!. Each piece is a small String that is copied into encoded and then dropped. That work is proportional to the piece, so the total stays linear.
    • Last expressions. encoded and strs have no semicolon, which makes them the values the methods return.

    Complexity

    Time: O(N) for each method, where N is the total length of the strings. encode copies each string once, plus a few digits for its length. decode moves j over each length prefix and copies each string once, and i only ever moves forward. With 100,000 strings of two or three characters each, the encoded text is 490,000 bytes long and decodes back to the same vector.

    Space: O(N) for the output of each method. No extra structure is needed beyond a few integers.

    Edge cases and common mistakes

    • Empty list against a list with one empty string. [] encodes to "" and decodes to []. [""] encodes to "0#" and decodes to a vector with one empty string. A scheme with no length-and-# for empty strings would merge the two.
    • Strings that look like the encoding. ["10#abc", "#", "12"] encodes to "6#10#abc1##2#12" and decodes correctly, because the decoder counts characters instead of interpreting what it reads.
    • Dropping the #. Writing only the length makes the boundary between a length and the string after it ambiguous.
    • Looking for the # from the wrong place. If the search for # started inside the string instead of at i, a # in the content would be mistaken for the marker.
    • Off-by-one in the slice. The string starts at j + 1, after the #, not at j.
    • Cutting the input down. Replacing s by the remainder after every piece copies the rest of the string each time, and makes decoding quadratic.

    Testing

    • ["lint", "code", "love", "you"] encodes to "4#lint4#code4#love3#you" and decodes back to the same four strings.
    • ["3#a", "", "#"] encodes to "3#3#a0#1##" and decodes back to the same three strings.
    • [] encodes to "" and decodes to [].
    • [""] encodes to "0#" and decodes to [""].
    • ["", ""] encodes to "0#0#" and decodes to two empty strings.
    Keep going with Rust500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free