LeetCode 394: Decode String Solution in Python – A Step-by-Step Guide

What Is LeetCode 394: Decode String?

LeetCode 394: Decode String provides an encoded string where digits represent repetition counts followed by substrings in brackets (e.g., "3[a]" means "aaa"). Your task is to decode it into the fully expanded string. It’s a problem that tests your ability to handle nested patterns and string construction efficiently!

Problem Statement

• Input:
• s: Encoded string (e.g., "3[a]2[bc]").
• Output: String - Decoded result (e.g., "aaabcbc").
• Rules:
• k[string] means repeat string k times.
• Brackets can be nested (e.g., "3[a2[c]]" → "accaccacc").
• Input is valid, digits are single or multi-digit.

Constraints

• 1 <= s.length <= 30
• s contains lowercase letters, digits, '[', ']'.
• Digits are 1-9, no leading zeros for multi-digit numbers.
• Valid encoding guaranteed.

Examples

• Input: s = "3[a]2[bc]"
• Output: "aaabcbc"
• "3[a]" → "aaa", "2[bc]" → "bcbc".
• Input: s = "3[a2[c]]"
• Output: "accaccacc"
• "2[c]" → "cc", "3[acc]" → "accaccacc".
• Input: s = "abc"
• Output: "abc"
• No brackets, no decoding.

These show the decoding puzzle—let’s solve it!

Understanding the Problem: Decoding Nested Strings

To tackle LeetCode 394 in Python, we need to: 1. Parse the string to identify numbers and bracketed substrings. 2. Handle nested brackets recursively or iteratively. 3. Build the decoded string efficiently.

A naive approach might process character-by-character without structure, but that’s messy. We’ll use:

• Best Solution: Stack—O(n) time, O(n) space—fast and iterative.
• Alternative Solution: Recursion—O(n) time, O(n) space—intuitive but recursive.

Let’s decode with the best solution!

Best Solution: Stack

Why This Is the Best Solution

The stack-based approach runs in O(n) time (n is string length) with O(n) space by processing the string in one pass, using stacks to track numbers and partial strings at each nesting level. It’s the most efficient—handling nested patterns iteratively without recursion’s overhead, making it both fast and clear!

How It Works

Think of it like stacking layers:

• Stacks:
• nums: Store repetition counts.
• strs: Store partial decoded strings.
• Process:
• Digit: Build number.
• '[': Push current number and string, reset.
• ']': Pop number and string, repeat and append.
• Letter: Append to current string.
• Result: Final decoded string.

It’s like building a string sandwich, layer by layer!

Step-by-Step Example

For s = "3[a]2[bc]":

• Init: nums = [], strs = [], curr_num = 0, curr_str = "".
• '3': curr_num = 3.
• '[': nums = [3], strs = [""], curr_num = 0, curr_str = "".
• 'a': curr_str = "a".
• ']': Pop 3 and "", curr_str = "" + "a" * 3 = "aaa", nums = [], strs = [].
• '2': curr_num = 2.
• '[': nums = [2], strs = ["aaa"], curr_num = 0, curr_str = "".
• 'b': curr_str = "b".
• 'c': curr_str = "bc".
• ']': Pop 2 and "aaa", curr_str = "aaa" + "bc" * 2 = "aaabcbc", nums = [], strs = [].
• Result: "aaabcbc".

For s = "3[a2[c]]":

• '3': curr_num = 3.
• '[': nums = [3], strs = [""], curr_num = 0, curr_str = "".
• 'a': curr_str = "a".
• '2': curr_num = 2.
• '[': nums = [3, 2], strs = ["", "a"], curr_num = 0, curr_str = "".
• 'c': curr_str = "c".
• ']': Pop 2 and "a", curr_str = "a" + "c" * 2 = "acc", nums = [3], strs = [""].
• ']': Pop 3 and "", curr_str = "" + "acc" * 3 = "accaccacc", nums = [], strs = [].
• Result: "accaccacc".

Code with Explanation

Here’s the Python code using a stack:

Copy codeclass Solution:
    def decodeString(self, s: str) -> str:
        # Stacks for numbers and strings
        nums = []
        strs = []
        curr_num = 0
        curr_str = ""

        # Process each character
        for char in s:
            if char.isdigit():
                # Build multi-digit number
                curr_num = curr_num * 10 + int(char)
            elif char == '[':
                # Push current state, reset
                nums.append(curr_num)
                strs.append(curr_str)
                curr_num = 0
                curr_str = ""
            elif char == ']':
                # Pop and decode
                num = nums.pop()
                prev_str = strs.pop()
                curr_str = prev_str + curr_str * num
            else:
                # Append letter
                curr_str += char

        return curr_str

Explanation

• Lines 4-7: nums: Stack for counts, strs: Stack for strings, curr_num, curr_str: Current state—O(1).
• Lines 9-23: Process string:
• Digit: Build number—O(1).
• '[': Push state, reset—O(1).
• ']': Pop, decode, combine—O(k) for repetition.
• Letter: Append to curr_str—O(1).
• Line 25: Return final string—O(1).
• Time: O(n)—single pass, repetition bounded by output size (still linear in practice).
• Space: O(n)—stack size up to nesting depth.

This is like a string stacker—fast and neat!

Alternative Solution: Recursion

Why an Alternative Approach?

The recursive solution also runs in O(n) time with O(n) space by parsing the string top-down, using recursion to handle nested brackets. It’s more intuitive—great for understanding the hierarchical structure, though it uses stack space and is less iterative than the best solution!

How It Works

• Recurse: Parse string, return decoded substring and next index.
• Base: Letters or end of string.
• Process: Handle numbers, brackets, recurse for nested parts.
• Result: Build decoded string.

Step-by-Step Example

For s = "3[a2[c]]":

• Parse(0):
• '3', '[' → num = 3, i = 2.
• Parse(2): "a2[c]":
• 'a', '2', '[' → num = 2, i = 4.
• Parse(4): "c]" → "c", i = 6.
• Back: "c" * 2 = "cc", i = 7.
• Back: "acc" * 3 = "accaccacc", i = 8.
• Result: "accaccacc".

Code with Explanation

Copy codeclass Solution:
    def decodeString(self, s: str) -> str:
        def decode(s, i):
            # Decode from index i, return string and next index
            result = ""
            num = 0

            while i < len(s):
                if s[i].isdigit():
                    num = num * 10 + int(s[i])
                elif s[i] == '[':
                    # Recurse for nested part
                    nested, next_i = decode(s, i + 1)
                    result += nested * num
                    num = 0
                    i = next_i
                elif s[i] == ']':
                    return result, i
                else:
                    result += s[i]
                i += 1

            return result, i

        # Start decoding from index 0
        decoded, _ = decode(s, 0)
        return decoded

Explanation

• Lines 3-21: decode(s, i):
• Build number—O(1).
• '[': Recurse, multiply result—O(k).
• ']': Return current result—O(1).
• Letter: Append—O(1).
• Line 24: Start at index 0—O(n).
• Time: O(n)—single pass, repetition bounded.
• Space: O(n)—recursion stack.

It’s a recursive decoder—clear but stacked!

Comparing the Two Solutions

• Stack (Best):
• Time: O(n)—linear.
• Space: O(n)—stack.
• Pros: Fast, iterative, concise.
• Cons: Stack management.
• Recursion (Alternative):
• Time: O(n)—linear.
• Space: O(n)—stack.
• Pros: Intuitive nesting.
• Cons: Recursion overhead.

Stack wins for efficiency and iteration!

Additional Examples and Edge Cases

• s="abc": Both return "abc".
• s="2[ab]": Both return "abab".
• Nested: Stack scales cleanly.

Stack is optimal, recursion works too.

Complexity Breakdown

• Stack:
• Time: O(n).
• Space: O(n).
• Recursion:
• Time: O(n).
• Space: O(n).

Stack excels for iterative simplicity.

Key Takeaways

• Stack: Decode iteratively—fast and neat!
• Recursion: Decode hierarchically—clear but stacked!
• Decoding: Structure drives solutions.
• Python Tip: Stacks rock—see [Python Basics](/python/basics).

Final Thoughts: Decode That String

LeetCode 394: Decode String in Python is a parsing challenge. Stack-based is the efficiency champ, while recursion offers an intuitive alternative. Want more? Try LeetCode 385: Mini Parser or LeetCode 20: Valid Parentheses. Ready to unravel? Visit Solve LeetCode 394 on LeetCode and decode that string today!