394.Decode String

Tags: [string], [encode], [decode], [stack]

Com: {g}

Link: https://leetcode.com/problems/decode-string/#/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 = []
        index = 0
        while index < len(s):
            curr = s[index]
            if curr == ']':
                buff = []
                while stack and stack[-1] != '[':
                    buff.append(stack.pop())
                stack.pop()
                buff.reverse()

                k_buff = []
                while stack and '0' <= stack[-1] <= '9':
                    k_buff.append(stack.pop())
                k_buff.reverse()
                k = int(''.join(k_buff))

                for _ in xrange(k):
                    for c in buff:
                        stack.append(c)
            else:
                stack.append(curr)

            index += 1

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

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

Revelation:

• The k times buff string should be put back into stack, because there exists the case: s = "3[a2[c]]".
• We need first build k_buff, then get k, because there exists the case s = "100[leetcode]".

Note:

• Time complexity = O(n), n is the length of the given string.
• Space complexity = O(n), n is the length of the given string.