Skip to main content

🟨 Encode and Decode Strings (#271) 🔒

🔗 Problem Link​

📋 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 encode and decode methods.

Note: This is a premium LeetCode problem, but available for free on NeetCode.

💡 Examples​

Example 1​

Input: ["neet","code","love","you"]
Output: ["neet","code","love","you"]

Explanation: encode() converts to a single string, decode() converts back

Example 2​

Input: ["we","say",":","yes"]
Output: ["we","say",":","yes"]

🔑 Key Insights & Approach​

Core Observation: Need a delimiter that won't conflict with string content.

Why Length Prefix?

  • Handles any character in strings (including delimiters)
  • Format: length#string for each word
  • Unambiguous parsing

Approaches:

  1. Length prefix encoding: 4#neet4#code
  2. Escape character (doesn't work for all cases)
  3. Non-ASCII delimiter (not universal)

Pattern: "Serialization/Encoding" pattern using length-based protocol.

🐍 Solution: Python​

Approach: Length Prefix Encoding​

Time Complexity: O(n) | Space Complexity: O(n)

from typing import List

class Solution:
    def encode(self, strs: List[str]) -> str:
        """Encodes a list of strings to a single string."""
        result = []
        for s in strs:
            # Format: length + '#' + string
            result.append(f"{len(s)}#{s}")
        return ''.join(result)

    def decode(self, s: str) -> List[str]:
        """Decodes a single string to a list of strings."""
        result = []
        i = 0

        while i < len(s):
            # Find the delimiter '#'
            j = i
            while s[j] != '#':
                j += 1

            # Extract length
            length = int(s[i:j])

            # Extract string of that length
            i = j + 1  # skip '#'
            result.append(s[i:i+length])
            i += length

        return result

🔵 Solution: Golang​

Approach: Length Prefix Encoding​

Time Complexity: O(n) | Space Complexity: O(n)

import (
    "strconv"
    "strings"
)

type Codec struct{}

func (codec *Codec) Encode(strs []string) string {
    var result strings.Builder

    for _, s := range strs {
        // Format: length + '#' + string
        result.WriteString(strconv.Itoa(len(s)))
        result.WriteString("#")
        result.WriteString(s)
    }

    return result.String()
}

func (codec *Codec) Decode(s string) []string {
    result := []string{}
    i := 0

    for i < len(s) {
        // Find delimiter
        j := i
        for s[j] != '#' {
            j++
        }

        // Extract length
        length, _ := strconv.Atoi(s[i:j])

        // Extract string
        i = j + 1
        result = append(result, s[i:i+length])
        i += length
    }

    return result
}

📚 References​