Decode String | LeetCode 75 | Python Stack Solution | Nested Encoding Handling |

Veröffentlicht am: 19 März 2025
auf dem Kanal: CodeVisium

181

In this LeetCode 75 problem, we are given an encoded string that follows the format k[encoded_string], where:

k is a positive integer specifying how many times the encoded_string should be repeated.
encoded_string may contain letters and can be nested inside other encoded strings.
Our task is to decode the string and return the final expanded version.
For example, given "3[a2[c]]", the correct output is "accaccacc".

Approach: Using a Stack 🏗️

To solve this problem efficiently, we use a stack-based approach. The reason a stack works well is that it helps us handle nested encodings by keeping track of intermediate states.

Step-by-Step Solution Explanation 🔍

1️⃣ Initialize Variables:

stack = [] → Used to store intermediate values (previous string state and repeat count).
curr_num = 0 → Used to track the current multiplier (k value before [).
curr_str = "" → Used to accumulate characters in the current segment.

2️⃣ Iterate Through Each Character in the String:

If the character is a digit (0-9):

Build curr_num by multiplying it by 10 and adding the current digit (to handle multi-digit numbers).
Example: "12[a]" → curr_num becomes 12.
If the character is [:

Push the current string (curr_str) and repeat count (curr_num) onto the stack.
Reset curr_str and curr_num to start a new encoded section.
If the character is ]:

Pop the last stored state (last_str, num) from the stack.
Decode the current segment by repeating curr_str num times.
Append the decoded part back to last_str.
If the character is a letter (a-z):

Simply append it to curr_str to continue building the current segment.

3️⃣ Final Result:

After processing all characters, curr_str holds the fully decoded string.

Python Code Implementation:

class Solution:
def decodeString(self, s):
stack = []
curr_num = 0
curr_str = ""

for char in s:
if char.isdigit():
curr_num = curr_num * 10 + int(char)
elif char == "[":
stack.append((curr_str, curr_num))
curr_str, curr_num = "", 0
elif char == "]":
last_str, num = stack.pop()
curr_str = last_str + num * curr_str
else:
curr_str += char

return curr_str

Example Test Cases

sol = Solution()
print(sol.decodeString("3[a]2[bc]")) # Output: "aaabcbc"
print(sol.decodeString("3[a2[c]]")) # Output: "accaccacc"
print(sol.decodeString("2[abc]3[cd]ef")) # Output: "abcabccdcdcdef"

Time & Space Complexity Analysis:
Time Complexity: O(n) 🔥

We iterate through the string once, and each character is processed at most twice (pushed/popped from stack).
Efficiently handles large strings due to linear complexity.
Space Complexity: O(n) 📦

Stack stores the intermediate states, so in the worst case (deeply nested encoding), we may store n/2 elements.

Example Walkthrough: "3[a2[c]]" 🛠️

Step 1: Stack stores intermediate states when [ appears.

char = '3' → curr_num = 3
char = '[' → stack = [("", 3)], curr_str = "", curr_num = 0
char = 'a' → curr_str = "a"
char = '2' → curr_num = 2
char = '[' → stack = [("", 3), ("a", 2)], curr_str = "", curr_num = 0
char = 'c' → curr_str = "c"
char = ']' → stack.pop() → last_str = "a", num = 2
→ curr_str = "a" + "cc" = "acc"
char = ']' → stack.pop() → last_str = "", num = 3
→ curr_str = "" + "accaccacc" = "accaccacc"

✅ Final Output: "accaccacc"

Why This Solution is Optimal? 💡

✔ Handles Nested Encodings Efficiently – Uses a stack to store previous states.
✔ Supports Multi-digit Multipliers – Correctly processes cases like "12[a]".
✔ Runs in O(n) Time – Fast and efficient for large inputs.
✔ Memory-Efficient – Uses stack space proportional to depth of nesting.

Auf dieser Seite können Sie das Online-Video Decode String | LeetCode 75 | Python Stack Solution | Nested Encoding Handling | mit der Dauer stunde minuten sekunde in guter Qualität ansehen, das der Benutzer CodeVisium 19 März 2025 hochgeladen hat, den Link mit Freunden und Bekannten teilen, dieses Video wurde auf Youtube bereits 181 Mal angesehen und es wurde von 2 den Zuschauern gefallen. Viel Spaß beim Betrachtenden Zuschauern gefallen!

1,612