📘 Problem Statement
Given an encoded string, return its decoded string. The encoding rule is as follows:
- k [encoded_string] means the encoded_string inside the square brackets is repeated exactly k times.
- The encoded string may contain digits, lowercase English letters, and square brackets.
You may assume that the input string is always valid, no extra white spaces, and no invalid characters. There are no leading zeros in the input string.
Your task is to implement a function decodeString(s: str) -> str to decode the input string.
📚 Example:
python
Input:
s = "3[a]2[bc]"
Output:
"aaabcbc"
python
Input:
s = "3[a2[c]]"
Output:
"accaccacc"
python
Input:
s = "2[abc]3[cd]ef"
Output:
"abcabccdcdcdef"
🧠 Key Insight
The main challenge is to correctly handle nested encoded strings. We need to decode them properly, respecting the levels of nesting. The task requires handling numbers (which denote the repetition count), characters (which are part of the encoded string), and brackets (which mark the start and end of sub-strings that need to be repeated).
💡 Approach
- Use a Stack for Decoding:
- Use a stack to handle the decoding process. As we encounter digits, letters, and brackets, we can use the stack to keep track of the current string and repetition factor.
- Process Each Character:
- Loop through the string:
- If we encounter a number, accumulate it (as it could have more than one digit).
- If we encounter an opening bracket
[, push the current string and the number to the stack.
- If we encounter a closing bracket
], pop the number and the string from the stack and repeat the substring accordingly.
- If we encounter a letter, add it to the current string.
- Form the Result:
- As we process the entire string, we build the final decoded string by applying the repetition factor to the substring enclosed within the brackets.
🐍 Python Code
python
class Solution:
def decodeString(self, s: str) -> str:
stack = []
current_string = ""
current_num = 0
for char in s:
if char.isdigit():
# Build the number for the repetition count
current_num = current_num * 10 + int(char)
elif char == '[':
# Push the current number and string to the stack
stack.append((current_string, current_num))
current_string, current_num = "", 0
elif char == ']':
# Pop from the stack and repeat the current string
prev_string, num = stack.pop()
current_string = prev_string + num * current_string
else:
# Append the current character to the current string
current_string += char
return current_string
🔍 Step-by-Step Explanation
1. Initialize Variables:
python
stack = []
current_string = ""
current_num = 0
- stack: Used to store the previous string and the current repetition number when we encounter an opening bracket
[.
- current_string: Used to build the decoded string as we process each character.
- current_num: Used to store the number (repetition count) when we encounter a digit.
2. Loop Through the Input String:
python
for char in s:
- We iterate through each character in the string
s.
3. Handle Digits:
python
if char.isdigit():
current_num = current_num * 10 + int(char)
- If the current character is a digit, we accumulate it to form the complete repetition count. For example, if the string contains
12[abc], we need to accumulate the digits 1 and 2 to form the number 12.
4. Handle Opening Bracket ([):
python
elif char == '[':
stack.append((current_string, current_num))
current_string, current_num = "", 0
- When we encounter an opening bracket
[, we push the current string and the repetition count to the stack and reset current_string and current_num to start processing the substring inside the brackets.
5. Handle Closing Bracket (]):
python
elif char == ']':
prev_string, num = stack.pop()
current_string = prev_string + num * current_string
- When we encounter a closing bracket
], we pop the previous string and the number from the stack. We repeat the current string num times and append it to the previous string.
6. Handle Letters:
python
else:
current_string += char
- If the character is a letter, we append it to the
current_string.
7. Return the Final Decoded String:
python
return current_string
- After processing all characters,
current_string will contain the fully decoded string, which we return.
💡 Example Walkthrough
Example 1:
python
Input:
s = "3[a]2[bc]"
Output:
"aaabcbc"
- Start with an empty string and num = 0.
- Processing
3[a]:
3 → current_num becomes 3.[ → Push ("", 3) to stack.a → Append a to current_string.] → Pop ("", 3) from stack, repeat a 3 times → "aaa".
- Processing
2[bc]:
2 → current_num becomes 2.[ → Push ("aaa", 2) to stack.b → Append b to current_string.c → Append c to current_string.] → Pop ("aaa", 2) from stack, repeat bc 2 times → "bcbc".
- Final Output: "aaabcbc".
Example 2:
python
Input:
s = "3[a2[c]]"
Output:
"accaccacc"
- Processing
3[a2[c]]:
3 → current_num becomes 3.[ → Push ("", 3) to stack.a → Append a to current_string.2 → current_num becomes 2.[ → Push ("a", 2) to stack.c → Append c to current_string.] → Pop ("a", 2) from stack, repeat c 2 times → "cc".] → Pop ("", 3) from stack, repeat "acc" 3 times → "accaccacc".
- Final Output: "accaccacc".
⏱️ Time & Space Complexity
MetricComplexityTime ComplexityO(n)Space ComplexityO(n)
- Time Complexity:
- We iterate through each character of the string once, so the time complexity is O(n), where n is the length of the string.
- Space Complexity:
- We use a stack to store intermediate strings and numbers, so the space complexity is O(n) in the worst case, where we store the entire string in the stack.
🧵 Final Thoughts
LeetCode 394 is an excellent problem to practice recursion and stack-based algorithms. The key challenge is efficiently handling nested structures with varying repetition counts. By using a stack to manage the intermediate state and properly processing digits, characters, and brackets, we can efficiently decode any valid encoded string.