# LeetCode 394. Decode String

## 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].

Examples:

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

## 描述

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

### 思路

• 使用栈,一个作为数字栈，用于存储数字，一个作为字符栈，用于存储字符；
• 如果遇到了数字，提取数字；
• 如果遇到 ‘[’ ，将数字压入栈，同时也将 ‘[’ 押入栈；
• 如果遇到 ‘]’ ，将栈中的字符从栈中压出，直到遇到了‘[’ ，将被压出的所有字符乘以数字栈中的最后一个字符，并压回栈。
```# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-08-25 09:19:03

class Solution:
def decodeString(self, s: str) -> str:
num, chr_stack, num_stack = 0, [], []
for char in s:
if char.isdigit():
num = num * 10 + int(char)
elif char == '[':
num_stack.append(num)
chr_stack.append("[")
num = 0
elif char == ']':
tmp = []
while chr_stack and chr_stack[-1] != '[':
tmp.append(chr_stack.pop())
chr_stack.pop()
chr_stack.extend(reversed(tmp * num_stack.pop()))
else:
chr_stack.append(char)

return "".join(chr_stack)

```