We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Encode and Decode Strings

Number: 271

Difficulty: Medium

Paid? Yes

Companies: Meta, Microsoft, OpenAI, Google, Snowflake, CrowdStrike, Amazon

Problem Description

Given a list of strings, design an algorithm to encode the list into a single string so that it can be transmitted over a network. Upon receipt, decode the string back into the original list of strings. The strings may contain any of the 256 valid ASCII characters, so make sure your encoding can handle all possible inputs.

Key Insights

  • Use length-prefix encoding for each string to avoid ambiguity.
  • Append a delimiter (e.g., "#") after the length to separate it from the string content.
  • This method ensures that even if the original strings contain special characters, including the delimiter, the decoding remains unambiguous.
  • The approach handles edge cases, such as empty strings.

Space and Time Complexity

Time Complexity: O(n), where n is the total number of characters across all strings. Space Complexity: O(n), required for the encoded string and the resulting decoded list.

Solution

We encode by iterating over each string and building a new string that contains the length of the string, a delimiter (e.g., "#"), and then the string itself. This way, during decoding, we can safely determine how many characters to extract by first reading until the delimiter to get the length, and then reading that number of characters. This length-prefix approach avoids conflicts with potential characters in the strings.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with line-by-line comments.

class Codec:
    # Encodes a list of strings to a single string.
    def encode(self, strs):
        encoded = []
        # Iterate through each string in the list.
        for s in strs:
            # Append the length of the string, a '#' as delimiter, and the string.
            encoded.append(str(len(s)) + '#' + s)
        # Join all parts into one encoded string.
        return ''.join(encoded)

    # Decodes a single string back to a list of strings.
    def decode(self, s):
        decoded = []
        i = 0  # Pointer to traverse the encoded string.
        while i < len(s):
            j = i
            # Find the '#' delimiter to determine the length.
            while s[j] != '#':
                j += 1
            # Convert the substring from i to j into an integer length.
            length = int(s[i:j])
            # Extract the actual string using the obtained length.
            string = s[j+1:j+1+length]
            decoded.append(string)
            # Move the pointer to the start of the next encoded segment.
            i = j + 1 + length
        return decoded

# Example usage:
# codec = Codec()
# encoded_str = codec.encode(["Hello", "World"])
# decoded_list = codec.decode(encoded_str)
← Back to All Questions