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

Pubblicato il: 19 marzo 2025
sul canale di: 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.

In questa pagina del sito puoi guardare il video online Decode String | LeetCode 75 | Python Stack Solution | Nested Encoding Handling | della durata di ore minuti seconda in buona qualità , che l'utente ha caricato CodeVisium 19 marzo 2025, condividi il link con amici e conoscenti, su youtube questo video è già stato visto 181 volte e gli è piaciuto 2 spettatori. Buona visione!

1,612