Start learning free

LESSON 323 OF 541 · HASH TABLE

Encode and Decode Strings in Swift: Length Prefixes, 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

    SWIFT · HASH TABLE

    Encode And Decode Strings in Swift, explained

    Problem overview

    The class Codec has two methods. encode(_ strs: [String]) -> String turns an array of strings into one string. decode(_ s: String) -> [String] receives only that string, from a different Codec object, and must rebuild the original array in the same order.

    The strings can hold any printable ASCII character, including #, digits and spaces, and a string 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##. An empty array encodes to the empty string, and [""] encodes to 0#, so the two stay different.

    Approach: write the length first

    The obvious plan is to put a separator between the strings and split on it. That fails here, because any character you pick can also appear inside a string. A string such as "#" would be cut in two.

    A length prefix avoids the problem. For each string, write its length, a #, and then the string. To decode, read digits up to the next #, convert them to a number length, and take exactly that many characters. Whatever those characters are, they belong to the current string, so the decoder never looks inside it. The next piece starts right after them.

    The # after the length matters. Without it, a string that begins with a digit would run into its own length: "12" after a length of 2 would read as 212. Digits contain no #, so the first # from the start of a piece is always the one encode wrote.

    Both methods must take O(N) time, where N is the total length of all the strings. That has two consequences. When encoding, append to one growing string rather than rebuilding it. When decoding, move an index through the data rather than cutting the string shorter after every piece.

    Step by step

    1. Start encoded as an empty string declared with var, because it grows.
    2. Loop over the strings with for s in strs.
    3. Append one piece per string: the length as text, then "#", then the string. s.count is an Int, so String(s.count) converts it.
    4. Return encoded after the loop.
    5. In decode, turn s into an array of characters. A Swift String can't be read at an integer position, but an array can, in constant time.
    6. Create the result array strs and an index i that starts at 0. It marks where the next piece begins.
    7. Loop while i < chars.count. Each round reads one piece.
    8. Find the #. Start j at i and advance it while chars[j] isn't "#". The characters in i..<j are the digits of the length.
    9. Convert the digits to a number. String(chars[i..<j]) builds a string from the slice, and Int(...) parses it into an optional, which ! unwraps because encode always wrote valid digits.
    10. Take the string itself: exactly length characters after the #, the range (j + 1)..<(j + 1 + length). Append it to strs.
    11. Move i to j + 1 + length, the start of the next piece.
    12. Return strs. For an empty s the loop never runs and the result is an empty array.

    The solution in Swift

    class Codec {
    func encode(_ strs: [String]) -> String {
        var encoded = ""
        for s in strs {
            encoded += String(s.count) + "#" + s
        }
        return encoded
    }

    func decode(_ s: String) -> [String] {
        let chars = Array(s)
        var strs = [String]()
        var i = 0
        while i < chars.count {
            var j = i
            while chars[j] != "#" {
                j += 1
            }
            let length = Int(String(chars[i..<j]))!
            strs.append(String(chars[(j + 1)..<(j + 1 + length)]))
            i = j + 1 + length
        }
        return strs
    }
}

    The Swift details worth a closer look:

    • Array(s) gives [Character]. Each element is one character as a person sees it, and count on a string counts characters in the same sense. Because encode and decode both count characters, the lengths agree even if a string holds an accented letter written as two Unicode scalars: "e\u{301}" has count 1, and it round-trips as one character.
    • Comparing with "#". In chars[j] != "#" the literal is read as a Character, because that is the element type.
    • Slices. chars[i..<j] is an ArraySlice<Character>, a view over part of the array. String(...) turns it into a string, copying only those characters.
    • The ! after Int(...). Int(String) returns nil when the text isn't a number, and ! would then crash. That can't happen for a string made by encode, but decoding arbitrary text this way would not be safe.
    • += on a string appends in place, so building the result costs time proportional to what is added.

    Tracing decode

    Here is decode on 3#3#a0#1##, the encoding of ["3#a", "", "#"]. The string has ten characters, at positions 0 to 9.

    ijlengthString takenNew i
    0133#a5
    560(empty)7
    781#10

    In the first round the inner loop stops at the # in position 1, so the length is 3, and the next three characters, 3#a, form the first string even though they contain a digit and a #. After the third round i is 10, which equals chars.count, so the outer loop ends.

    Complexity

    Time: O(N). encode appends each string once, and writing a length costs only a few digits. decode copies the string into an array once, and every character is then passed over once: either as part of a length, scanned by the inner loop, or as part of a string, skipped by jumping i forward and copied once into its result string.

    Space: O(N) for the encoded string, the character array and the output.

    Edge cases and common mistakes

    • No strings. [] encodes to "" and decodes to [].
    • One empty string. [""] encodes to 0#. The decoder reads length 0, takes zero characters and appends an empty string.
    • Strings that look like lengths. ["3#a", "", "#"] works because the decoder trusts the length and never inspects the contents.
    • Dropping the #. Then ["1", "23"] becomes 1123, and there is no way to tell where the lengths end.
    • Cutting s down. Rebuilding the remaining string after every piece copies the rest of the data each time, which is quadratic for many strings. The index avoids that.

    Testing

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