题目描述：

LeetCode 394. Decode String

Given an encoded string, return it's 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].

Examples:

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

题目大意：

给定一个经过编码的字符串，返回其解码字符串。

编码规则为：k[encoded_string]，其中中括号内的encoded_string被重复k次。注意k一定是正整数。

你可以假设输入字符串总是有效的；没有额外的空白字符，中括号也是格式良好的，等等。

另外，你可以假设原始数据不包含数字，并且数字只用来表示重复的次数，k。例如，输入不会出现3a或者2[4]等等。

解题思路：

利用栈（Stack）数据结构。

当出现左括号时，将字符串压栈。

当出现右括号时，将字符串弹栈，并重复响应次数，累加至新的栈顶元素。

Python代码：

class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        k = 1
        parts = collections.defaultdict(str)
        digits = collections.defaultdict(int)
        for c in s:
            if c.isdigit():
                digits[k] = digits[k] * 10 + int(c)
            elif c == '[':
                k += 1
            elif c == ']':
                parts[k - 1] += digits[k - 1] * parts[k]
                digits[k - 1] = 0
                parts[k] = ''
                k -= 1
            else:
                parts[k] += c
        return parts[1]

 

本文链接：http://bookshadow.com/weblog/2016/09/04/leetcode-decode-string/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码