MediumBlind75StringDesign

Encode and Decode Strings

Design an algorithm to encode a list of strings to a single string, and decode that single string back to the original list of strings.

Examples

Input
encode(["neet","code","love","you"])
Output
4#neet4#code4#love3#you

Each string is prefixed with its length followed by '#'.

Input
decode("4#neet4#code4#love3#you")
Output
["neet","code","love","you"]

Read the length, then read that many characters.

Constraints

  • •1 <= strs.length <= 200
  • •0 <= strs[i].length <= 200
  • •strs[i] contains any possible characters out of 256 valid ASCII characters.

Approaches

Use a special delimiter character that doesn't appear in the strings.

CodeT: O(n * k) | S: O(n * k)
def encode(strs):
    return '|'.join(strs)

def decode(s):
    if not s:
        return []
    return s.split('|')

Escape the delimiter character within strings.

CodeT: O(n * k) | S: O(n * k)
def encode(strs):
    return ''.join(s.replace('|', '||') + '|' for s in strs)

def decode(s):
    if not s:
        return []
    result = []
    current = ''
    i = 0
    while i < len(s):
        if s[i] == '|':
            if i + 1 < len(s) and s[i+1] == '|':
                current += '|'
                i += 2
            else:
                result.append(current)
                current = ''
                i += 1
        else:
            current += s[i]
            i += 1
    return result

Encode each string with its length followed by a '#' delimiter.

Diagram

strs = ['neet','code'] Encode: '4#neet4#code' Decode: read '4' -> length=4, read 'neet'
CodeT: O(n * k) | S: O(n * k)
def encode(strs):
    result = ''
    for s in strs:
        result += str(len(s)) + '#' + s
    return result

def decode(s):
    result = []
    i = 0
    while i < len(s):
        j = i
        while s[j] != '#':
            j += 1
        length = int(s[i:j])
        result.append(s[j+1:j+1+length])
        i = j + 1 + length
    return result

Complexity Comparison

Delimiter-Based Encoding
T: O(n * k)S: O(n * k)

Use a special delimiter character that doesn't appear in the strings.

Escape Characters
T: O(n * k)S: O(n * k)

Escape the delimiter character within strings.

Length-Prefix Encoding
T: O(n * k)S: O(n * k)

Encode each string with its length followed by a '#' delimiter.

Common Mistakes

Using a simple delimiter without handling it appearing within strings

Not handling empty strings in the input list

Off-by-one errors when parsing the length prefix

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems