394. Decode String (Python)

Related Topic

Stack.

Description

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; 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 won’t be input like 3a or 2[4].

Sample I/O

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"

Example 4

Input: s = "abc3[cd]xyz"
Output: "abccdcdcdxyz"

Methodology

There are four types of elements in a string.

1. If the current char is digit (could be more than 10) we need to convert to int and assign to number
2. If the current char is ‘[’ we need to append the previous string and the number to stack and those two will combine to be previous string for later use and clear string (become ‘’) and number (become 0)
3. If the current char is alphabet, we need to concatenate the char to string.
4. If the current char is ‘]’ we pop out the previous string and previous number and convert to new string by previous string + number * current string then assign to string for future use After iterate all elements, we return the string as result.

def decodeString(self, s: str) -> str:
        num = 0
        string = ''
        stack = []
        for c in s:
            if c.isdigit():
                num = num*10 + int(c)
            elif c == "[":
                stack.append(string)
                stack.append(num)
                string = ''
                num = 0
            elif c.isalpha():
                string += c
            elif c == ']':
                pre_num = stack.pop()
                pre_string = stack.pop()
                string = pre_string + pre_num * string
        return string

BigO

Iterate the string once so it take O(n) time complexity.