TIC
The Interns Company

Encode and Decode Strings

MediumAcceptance: 37.5%
StringDesignArray

Problem Statement

Design an algorithm to encode a list of strings to a single string. The encoded string is then decoded back to the original list of strings. Implement the encode and decode methods.

Constraints:

  • 1 <= strs.length <= 150
  • 0 <= strs[i].length <= 150
  • strs[i] consists of any Unicode character
  • No restriction on the characters used in the input

Input Format:

  • A list of strings to encode or a single encoded string to decode

Output Format:

  • For encode: Return a single string that encodes the input list of strings
  • For decode: Return the original list of strings from the encoded string

Examples:

Example 1:

Input:

encode(["Hello", "World"])

Output:

"5#Hello5#World"

Explanation:

The encoded string represents the original array ["Hello", "World"].

Example 2:

Input:

decode("5#Hello5#World")

Output:

["Hello", "World"]

Explanation:

The decode function successfully recovers the original array from the encoded string.

Example 3:

Input:

encode(["abc", "", "d"])

Output:

"3#abc0#1#d"

Explanation:

The encoded string represents the original array ["abc", "", "d"] with empty string properly handled.

Solutions

Length Prefixing with Delimiter

Time: O(n) where n is the total length of all strings in the list
Space: O(n) for storing the encoded string or the decoded list

Encode each string by prefixing it with its length followed by a special delimiter (e.g., '#'). For decoding, parse the length prefix to determine how many characters to read for each string.

Escape Characters Approach

Time: O(n) where n is the total length of all strings in the list
Space: O(n) for storing the encoded string or the decoded list

Use an escape character to handle delimiters within the strings. This approach is useful when the delimiter might appear in the strings themselves.

Chunked Transfer Encoding

Time: O(n) where n is the total length of all strings in the list
Space: O(n) for storing the encoded string or the decoded list

Similar to how HTTP chunked transfer encoding works, each string is preceded by its length in hexadecimal followed by a delimiter and then the actual content.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

  1. To encode ["Hello", "World"] with the length prefixing approach:
  2. String "Hello" has length 5, so we encode it as "5#Hello"
  3. String "World" has length 5, so we encode it as "5#World"
  4. Combine them: "5#Hello5#World"
  5. To decode "5#Hello5#World":
  6. Read the length of the first string: 5
  7. Read the next 5 characters: "Hello"
  8. Move to the next position
  9. Read the length of the next string: 5
  10. Read the next 5 characters: "World"
  11. Result: ["Hello", "World"]

Hints

Hint 1
Think about how to uniquely represent the boundaries between different strings in the encoded output.
Hint 2
What if the strings themselves contain the character you are using as a delimiter?
Hint 3
One approach is to include both the length of each string and a delimiter.
Hint 4
Using string length as metadata helps in unambiguously parsing the encoded string during decoding.
Hint 5
Consider how to handle edge cases like empty strings.

Video Tutorial

Encode and Decode Strings - Length Prefixing Approach

YouTube•Learn the Encode and Decode Strings solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the encoding and decoding process, showing how each string is transformed during encoding and recovered during decoding.

Key visualization elements:

  • length prefix
  • delimiter
  • string content

Similar Questions

Serialize and Deserialize Binary Tree

Hard

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Asked By

GoogleFacebookAmazonMicrosoftUberAirbnbDropbox

Implementation Notes

This problem tests understanding of string manipulation, parsing, and design. The key insight is choosing an encoding scheme that unambiguously represents the boundaries between strings.