394.Decode String

Tags: [stack], [expression], [decode]

Link: https://leetcode.com/problems/decode-string/?tab=Description

Given an encoded string, return it's decoded string.

The encoding rule is:k[encoded_string], where theencoded_stringinside the square brackets is being repeated exactlyktimes. Note thatkis 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 like3aor2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

Solution: stack

class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s:
            return s

        stack = []
        for c in s:
            if not stack or c != ']':
                stack.append(c)
            else:
                # c == ']'
                buff = []
                while stack and stack[-1] != '[':
                    buff.append(stack.pop())
                stack.pop()

                repeated_times_num_buff = []
                while stack and '0' <= stack[-1] <= '9':
                    repeated_times_num_buff.append(stack.pop())

                repeated_times_num_buff.reverse()
                repeated_times = int(''.join(repeated_times_num_buff))

                buff.reverse()
                tmp_result = buff * repeated_times
                for tmp_c in tmp_result:
                    stack.append(tmp_c)

        result = []
        while stack:
            result.append(stack.pop())

        result.reverse()
        return ''.join(result)

Note:

• Time complexity = O(n), n is the length of the given string.
• We need to build the repeated times num char by char.