LeetCode 604: Design Compressed String Iterator Solution in Python – A Step-by-Step Guide

What Is LeetCode 604: Design Compressed String Iterator?

In LeetCode 604: Design Compressed String Iterator, you’re tasked with designing a class, StringIterator, that takes a compressed string (e.g., "L1e2t1") and provides two methods: next() to return the next character (or a space if done), and hasNext() to check if more characters remain. The string is compressed with letters followed by numbers (e.g., "L10" means 10 'L's). For "L1e2t1", you’d get "L", "e", "e", "t", then spaces. This problem tests your ability to manage state and iterate efficiently, blending string parsing with object-oriented design.

Problem Statement

• Input: A compressed string (e.g., "L1e2t1").
• Output: A class with:
• next(): Returns the next character or ' ' if exhausted.
• hasNext(): Returns True if characters remain, False otherwise.
• Rules:
• Format: Letter followed by a number (1 to 10⁹).
• Numbers indicate how many times the letter repeats.

Constraints

• String length: 1 to 1000.
• Each number: 1 to 10⁹.
• next() and hasNext() called up to 10⁵ times.

Examples

• Input: "L1e2t1"
• next(): 'L', 'e', 'e', 't', ' ', ' '...
• hasNext(): True, True, True, True, False...
• Input: "a12b56c1"
• next(): 'a', 'a', ..., 'b', ..., 'c', ' '...
• hasNext(): True (13 times), False...

These examples show the flow—let’s build it!

Understanding the Problem: Iterating a Compressed String

To solve LeetCode 604: Design Compressed String Iterator in Python, we need a class that initializes with a compressed string and tracks its state to deliver characters one-by-one. A naive approach might decompress the whole string upfront, but that’s wasteful with memory (imagine "a1000000"). Instead, we’ll use:

• Best Solution (Pointer-Based Parsing): O(1) amortized time per call, O(1) space—fast and lean.
• Alternative Solution (Pre-Decompressed List): O(n) preprocessing time, O(m) space (m = decompressed length)—simple but heavy.

Let’s start with the pointer-based solution, breaking it down for beginners.

Best Solution: Pointer-Based Iteration with Parsing

Why This Is the Best Solution

The pointer-based approach is the top choice for LeetCode 604 because it’s efficient—O(1) amortized time per next() call and O(1) space—and avoids decompressing the string. It uses pointers to track the current position in the compressed string, parsing letters and counts as needed. It’s like reading a coded message one piece at a time, only decoding what you need!

How It Works

Think of this as stepping through a coded scroll:

• Step 1: Initialize:
• Store the compressed string.
• Use pointers: pos (current index), count (remaining repeats), char (current letter).
• Step 2: Next():
• If count > 0, return char and decrement count.
• If count = 0, move pos to next letter, parse its number, update char and count.
• Return space if exhausted.
• Step 3: HasNext():
• Check if count > 0 or pos < string length.
• Step 4: Parse Numbers:
• Extract digits after a letter dynamically.

It’s like decoding on demand—smart and sleek!

Step-by-Step Example

Example: "L1e2t1"

• Init: s = "L1e2t1", pos = 0, count = 0, char = ''.
• next():
• count = 0, pos = 0: Parse "L1", char = 'L', count = 1.
• Return 'L', count = 0.
• next():
• pos = 2: Parse "e2", char = 'e', count = 2.
• Return 'e', count = 1.
• next():
• Return 'e', count = 0.
• next():
• pos = 4: Parse "t1", char = 't', count = 1.
• Return 't', count = 0.
• next():
• pos = 6: Beyond length, return ' '.
• hasNext():
• True until count = 0 and pos >= len(s).

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass StringIterator:
    def __init__(self, compressedString: str):
        # Step 1: Initialize state
        self.s = compressedString
        self.pos = 0           # Current position in string
        self.count = 0         # Remaining repeats of current char
        self.char = ' '        # Current character
        self.length = len(self.s)

    def next(self) -> str:
        # Step 2: Return next character
        if self.count == 0 and self.pos < self.length:
            # Parse new letter and count
            self.char = self.s[self.pos]
            self.pos += 1
            num = 0
            while self.pos < self.length and self.s[self.pos].isdigit():
                num = num * 10 + int(self.s[self.pos])
                self.pos += 1
            self.count = num

        # Return current char or space if done
        if self.count > 0:
            self.count -= 1
            return self.char
        return ' '

    def hasNext(self) -> bool:
        # Step 3: Check if more characters remain
        return self.count > 0 or self.pos < self.length

• Lines 3-8: __init__:
• Store string, set initial state.
• Lines 11-20: next:
• If count = 0 and more to parse:
• Get letter at pos.
• Parse following digits into num.
• Update char and count.
• If count > 0, return char and decrement.
• Else, return space.
• Line 25: hasNext:
• True if count > 0 or unparsed string remains.
• Time Complexity: O(1) amortized per call—parsing is spread out.
• Space Complexity: O(1)—just a few variables.

This is like a string decoder—light and fast!

Alternative Solution: Pre-Decompressed List

Why an Alternative Approach?

The pre-decompressed list approach builds a full list of characters upfront—O(n) preprocessing time, O(m) space (m = decompressed length). It’s simpler to understand and implement, but it’s memory-intensive, especially for large counts (e.g., "a1000000"). It’s like unrolling the entire scroll before reading it!

How It Works

Picture this as unpacking everything first:

• Step 1: Decompress the string into a list.
• Step 2: Use an index to track position.
• Step 3: next() returns the next char or space.
• Step 4: hasNext() checks if index is within bounds.

It’s like laying out all seats before picking one!

Step-by-Step Example

Example: "L1e2t1"

• Init: Decompress to ['L', 'e', 'e', 't'], idx = 0.
• next():
• idx = 0: 'L', idx = 1.
• idx = 1: 'e', idx = 2.
• idx = 2: 'e', idx = 3.
• idx = 3: 't', idx = 4.
• idx = 4: ' '.
• hasNext(): True until idx = 4.

Code for List Approach

Copy codeclass StringIterator:
    def __init__(self, compressedString: str):
        self.chars = []
        i = 0
        while i < len(compressedString):
            char = compressedString[i]
            i += 1
            num = 0
            while i < len(compressedString) and compressedString[i].isdigit():
                num = num * 10 + int(compressedString[i])
                i += 1
            self.chars.extend([char] * num)
        self.idx = 0

    def next(self) -> str:
        if self.idx < len(self.chars):
            char = self.chars[self.idx]
            self.idx += 1
            return char
        return ' '

    def hasNext(self) -> bool:
        return self.idx < len(self.chars)

• Lines 4-12: Decompress into chars.
• Lines 15-19: next: Return char or space.
• Line 22: hasNext: Check index.
• Time Complexity: O(n) preprocessing, O(1) per call.
• Space Complexity: O(m)—decompressed length.

It’s a full unpack—easy but heavy!

Comparing the Two Solutions

• Pointer-Based (Best):
• Pros: O(1) amortized time, O(1) space, memory-efficient.
• Cons: Parsing logic.
• List (Alternative):
• Pros: O(n) preprocess, O(1) per call, simple.
• Cons: O(m) space, impractical for large counts.

Pointer wins for efficiency.

Additional Examples and Edge Cases

• Input: "a1", next(): 'a', ' '.
• Input: "x10", next(): 10 'x’s, then ' '.

Both handle these, but pointer scales better.

Complexity Breakdown

• Pointer: Time O(1) amortized, Space O(1).
• List: Time O(n) preprocess, Space O(m).

Pointer is optimal.

Key Takeaways

• Pointer: On-the-fly parsing—smart!
• List: Pre-unpack—clear!
• Iterators: State management is fun.
• Python Tip: Strings rock—see Python Basics.

Final Thoughts: Decode That String

LeetCode 604: Design Compressed String Iterator in Python is a neat design challenge. The pointer approach offers speed and elegance, while the list method keeps it simple. Want more? Try LeetCode 281: Zigzag Iterator or LeetCode 341: Flatten Nested List Iterator. Ready to iterate? Head to Solve LeetCode 604 on LeetCode and unpack that string today!