How do you solve Decode String on LeetCode?

Decode String (LeetCode #394) can be solved using Optimal Solution. The optimal approach is Optimal Solution with Unknown time complexity and Unknown space complexity. Key insight: The optimal solution uses a stack to handle nested structures efficiently. By pushing characters and numbers onto the stack, we can build the decoded string in a single pass without needing to repeatedly expand substrings.

What is the time complexity of Decode String?

The optimal solution for Decode String runs in Unknown time and uses Unknown space.

What algorithm or data structure is used to solve Decode String?

Decode String uses the following concepts: String, Stack, Recursion. The recommended patterns to study are: Stack, Recursion.

What are the interview tips for Decode String?

Clarify the input format and constraints before starting Think about edge cases, such as empty strings or deeply nested structures Practice writing code with a focus on readability and maintainability

What are common mistakes when solving Decode String?

Forgetting to handle nested brackets properly Not managing the current number correctly when digits are multiple characters

Decode String — LeetCode #394 (Medium)

Tags: String, Stack, Recursion

Related patterns: Stack, Recursion

Optimal Solution approach

Time complexity: Unknown. Space complexity: Unknown.

The optimal solution uses a stack to handle nested structures efficiently. By pushing characters and numbers onto the stack, we can build the decoded string in a single pass without needing to repeatedly expand substrings.

Step 1: Initialize a stack to keep track of characters and numbers.
Step 2: Traverse the input string character by character.
Step 3: When a digit is encountered, build the full number and push it onto the stack.
Step 4: When a '[ 'is encountered, push it onto the stack to mark the start of a new substring.
Step 5: When a ']' is encountered, pop from the stack until the corresponding '[' is found, and repeat the substring based on the last number popped from the stack.
Step 6: Continue until the entire string is processed, then join the stack to form the final result.

Common Mistakes

Forgetting to handle nested brackets properly
Not managing the current number correctly when digits are multiple characters

Interview Tips

Clarify the input format and constraints before starting
Think about edge cases, such as empty strings or deeply nested structures
Practice writing code with a focus on readability and maintainability

#394

Decode String

Medium

String↗Stack↗Recursion↗Stack↗Recursion↗

LeetCode ↗

Approaches

💡

Intuition

Time UnknownSpace Unknown

⚙️

Algorithm

6 steps

1Step 1: Initialize a stack to keep track of characters and numbers.
2Step 2: Traverse the input string character by character.
3Step 3: When a digit is encountered, build the full number and push it onto the stack.
4Step 4: When a '[ 'is encountered, push it onto the stack to mark the start of a new substring.
5Step 5: When a ']' is encountered, pop from the stack until the corresponding '[' is found, and repeat the substring based on the last number popped from the stack.
6Step 6: Continue until the entire string is processed, then join the stack to form the final result.

solution.py21 lines

1# Full working Python code
2
3def decodeString(s):
4    stack = []
5    current_num = 0
6    current_str = ''
7    for char in s:
8        if char.isdigit():
9            current_num = current_num * 10 + int(char)
10        elif char == '[':
11            stack.append((current_str, current_num))
12            current_str, current_num = '', 0
13        elif char == ']':
14            last_str, num = stack.pop()
15            current_str = last_str + current_str * num
16        else:
17            current_str += char
18    return current_str
19
20# Example usage
21print(decodeString('3[a2[c]]'))

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.