LeetCode 271: Encode and Decode Strings Solution in Python – A Step-by-Step Guide

What Is LeetCode 271: Encode and Decode Strings?

In LeetCode 271: Encode and Decode Strings, you’re tasked with creating two methods: encode, which takes a list of strings and turns it into one string, and decode, which reverses the process to retrieve the original list. The encoded string must contain all the information needed to rebuild the list exactly, even with empty strings or special characters. This problem introduces string manipulation and serialization, related to challenges like LeetCode 394: Decode String, but focuses on list encoding rather than pattern repetition.

Problem Statement

• Input: For encode, a list of strings strs; for decode, a single string.
• Output: For encode, a single string; for decode, the original list of strings.
• Rules: Encoding must be reversible; handle empty strings and special characters; design your own format.

Constraints

• strs.length: 0 to 200.
• strs[i].length: 0 to 200.
• Strings contain any ASCII characters.

Examples

• Input: strs = ["Hello", "World"]
• Encode: "5:Hello5:World"
• Decode: ["Hello", "World"]
• Input: strs = [""]
• Encode: "0:"
• Decode: [""]
• Input: strs = ["C#", "&"]
• Encode: "2:C#1:&"
• Decode: ["C#", "&"]

Understanding the Problem: Packing and Unpacking Strings

To solve LeetCode 271: Encode and Decode Strings in Python, we need to turn a list of strings into one string (encode) and then break it back into the original list (decode). The encoded string must carry enough info—like string lengths or separators—to rebuild the list exactly, even with empty strings or odd characters (e.g., "#"). A basic way—joining strings directly—won’t work because we’d lose track of where one ends and another begins. We’ll use two methods: 1. Best Solution (Length-Prefix Encoding): O(n) time—fast and robust. 2. Alternative Solution (Delimiter-Based Encoding): O(n) time—simple but needs escaping.

Let’s dive into the best solution with a friendly, detailed walkthrough.

Best Solution: Length-Prefix Encoding

Why This Is the Best Solution

The length-prefix encoding approach is the top pick for LeetCode 271 because it runs in O(n) time—where n is the total length of all strings—and uses a clean, reliable format: each string is prefixed with its length followed by a colon (e.g., "5:Hello"). It’s space-efficient, avoids delimiter conflicts, and handles any character, making it both fast and foolproof.

How It Works

Think of this solution as packing a suitcase: for each string, write down how many letters it has (its length), add a little marker (":"), then toss in the string itself. To unpack, read the length, grab that many characters, and move on. Here’s how it works, step-by-step, explained simply:

• Step 1: Encode the List:
• For each string in strs:
• Get its length (e.g., "Hello" → 5).
• Format as "length:string" (e.g., "5:Hello").
• Join all formatted pieces into one string (e.g., "5:Hello5:World").
• Step 2: Decode the String:
• Start at the beginning:
• Find the first colon—before it is the length (e.g., "5").
• Take that many characters after the colon (e.g., "Hello").
• Move past this string and repeat until done.
• Step 3: Why It Works:
• The length tells us exactly where each string ends, so no confusion—even with empty strings ("0:") or special characters ("2:C#").
• Step 4: Handle Edge Cases:
• Empty list → empty string; empty string in list → "0:".

It’s like labeling boxes—size first, contents next, so unpacking is a breeze!

Step-by-Step Example

Example: strs = ["Hello", "World"]

• Encode:
• "Hello": Length = 5, "5:Hello".
• "World": Length = 5, "5:World".
• Join: "5:Hello5:World".
• Decode:
• Start: "5:Hello5:World".
• First length = 5, take 5 chars after ":" → "Hello", move to "5:World".
• Next length = 5, take 5 chars → "World", done.
• Result: ["Hello", "World"].

Example: strs = ["C#", "&"]

• Encode:
• "C#": Length = 2, "2:C#".
• "&": Length = 1, "1:&".
• Join: "2:C#1:&".
• Decode:
• "2:C#1:&" → Length = 2, "C#", move to "1:&".
• Length = 1, "&", done.
• Result: ["C#", "&"].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained in a friendly way:

Copy codeclass Codec:
    def encode(self, strs: List[str]) -> str:
        # Step 1: Encode each string with length prefix
        encoded = []
        for s in strs:
            encoded.append(f"{len(s)}:{s}")

        # Step 2: Join into one string
        return "".join(encoded)

    def decode(self, s: str) -> List[str]:
        # Step 3: Handle empty string
        if not s:
            return []

        # Step 4: Decode by parsing lengths
        result = []
        i = 0
        while i < len(s):
            # Find colon
            colon = s.find(":", i)
            length = int(s[i:colon])  # Get length before colon
            # Take next 'length' chars
            start = colon + 1
            end = start + length
            result.append(s[start:end])
            i = end  # Move to next segment

        return result

• Encode:
• Line 3-6: Loop through strs, format each as "length:string".
• Line 8: Join all pieces into one string.
• Decode:
• Line 11-12: If input is empty, return empty list.
• Line 15-23: While not at end:
• Find next colon, extract length.
• Slice out the string of that length, add to result.
• Move index past this string.
• Time Complexity: O(n)—one pass to encode, one to decode (n is total length).
• Space Complexity: O(n)—result list and encoded string.

This solution is like a tidy mail system—label and pack, then unpack with ease!

Alternative Solution: Delimiter-Based Encoding

Why an Alternative Approach?

The delimiter-based encoding method uses a special character (like "#") to separate strings, like putting dividers between book chapters. It’s O(n) time too but requires handling the delimiter in the strings themselves, making it simpler to start with but trickier with special cases.

How It Works

Think of this as taping strings together with a marker between them: join with a delimiter, then split on it to get them back. If the delimiter appears in the strings, escape it (e.g., replace "#" with "##"). Here’s how it works, step-by-step:

• Step 1: Encode by joining with "#", escaping "#" in strings.
• Step 2: Decode by splitting on "#", unescaping as needed.
• Step 3: Handle empty strings with a special case.

It’s like string glue—stick them together, peel them apart!

Step-by-Step Example

Example: strs = ["C#", "&"]

• Encode:
• "C#" → "C##" (escape #).
• "&" → "&".
• Join: "C###&".
• Decode:
• Split "C###&" on "#" → ["C", "", "&"].
• Unescape: "C#" (combine "C" and ""), "&".
• Result: ["C#", "&"].

Code for Delimiter Approach

Copy codeclass Codec:
    def encode(self, strs: List[str]) -> str:
        # Step 1: Escape and join
        escaped = [s.replace("#", "##") for s in strs]
        return "#".join(escaped)

    def decode(self, s: str) -> List[str]:
        # Step 2: Split and unescape
        if not s:
            return []
        split = s.split("#")
        result = []
        i = 0
        while i < len(split):
            curr = split[i]
            if i + 1 < len(split) and split[i + 1] == "":
                curr += "#"
                i += 1
            result.append(curr)
            i += 1
        return result

• Time Complexity: O(n)—pass for escaping and splitting.
• Space Complexity: O(n)—result and temp strings.

It’s a clear join but needs escaping care.

Comparing the Two Solutions

• Best Solution (Length-Prefix):
• Pros: O(n) time, O(n) space, robust, no escaping.
• Cons: Parsing logic to learn.
• Alternative Solution (Delimiter):
• Pros: O(n) time, O(n) space, simple idea.
• Cons: Escaping complexity, delimiter conflicts.

Length-prefix wins for reliability.

Additional Examples and Edge Cases

Empty List

• [] → "" → []

Empty String

• [""] → "0:" → [""]

Special Chars

• ["a#b", "c"] → "3:a#b1:c" → ["a#b", "c"]

Both handle these well.

Complexity Breakdown

• Length-Prefix:
• Time: O(n)—linear passes.
• Space: O(n)—output.
• Delimiter:
• Time: O(n)—linear passes.
• Space: O(n)—output.

Length-prefix is cleaner.

Key Takeaways

• Length-Prefix: Size guides decoding.
• Delimiter: Markers need care.
• Encoding: Pack smartly.
• Python Tip: Strings flex with f-strings—see [Python Basics](/python/basics).

Final Thoughts: Encode Like a Pro

LeetCode 271: Encode and Decode Strings in Python is a fun string-packing adventure. The length-prefix solution zips up strings cleanly, while the delimiter method offers a basic glue. Want more? Try LeetCode 394: Decode String or LeetCode 535: Encode and Decode TinyURL. Ready to pack? Head to Solve LeetCode 271 on LeetCode and encode those strings today!