[LeetCode] 394. Decode String

1. Question

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].

The test cases are generated so that the length of the output will never exceed 105.

Example 1:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Example 2:

Input: s = "3[a2[c]]"
Output: "accaccacc"

Example 3:

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

2. Thoughts

Went straight to the problem.

3. Tips learned

4. My solution

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        stack2 = []
        final_string = ""
        sub_string = ""
        i = 0
        while i < len(s):
            if s[i].isdigit():
                count = s[i]
                while s[i + 1].isdigit():
                    i += 1
                    count += s[i]
                stack.append(int(count))

            elif s[i] == "[":
                stack2.append(sub_string)
                sub_string = ""

            elif s[i] == "]":
                sub_string = sub_string * int(stack[-1])
                sub_string = stack2[-1] + sub_string
                stack.pop()
                stack2.pop()

                # empty
                if not stack:
                    final_string += sub_string
                    sub_string = ""

            else:
                sub_string += s[i]

            i += 1

        return final_string + sub_string

34/34 cases passed (40 ms)
Your runtime beats 42.09 % of python3 submissions
Your memory usage beats 8.69 % of python3 submissions (16.3 MB)

5. AI Solution and Improvements

Your solution for decoding the encoded string is quite comprehensive and handles the nested encoding correctly. However, it can be simplified and made more efficient by using a single stack to keep track of both the counts and the substrings. This approach avoids the need for two separate stacks and simplifies the logic for building the final string.

Here's a revised version of your code with these improvements:

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        current_string = ""
        k = 0

        for char in s:
            if char.isdigit():
                k = k * 10 + int(char)  # To handle multi-digit numbers
            elif char == '[':
                # Push the current state onto the stack
                stack.append((current_string, k))
                current_string, k = "", 0
            elif char == ']':
                # Pop the last state and combine
                last_string, last_k = stack.pop()
                current_string = last_string + last_k * current_string
            else:
                current_string += char

        return current_string

In this revised version:

• We keep track of the current substring and the current count (k).
• When we encounter an opening bracket [, we push the current state (current_string and k) onto the stack and reset them for the next substring.
• When we encounter a closing bracket ], we pop the last state from the stack and combine it with the current substring.
• We handle multi-digit numbers by multiplying the previous k by 10 and adding the current digit.
• The final decoded string is stored in current_string.

This approach is cleaner and more efficient, as it directly constructs the final string without requiring a separate final_string variable.