> For the complete documentation index, see [llms.txt](https://zhongwen.gitbook.io/leetcode-report/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zhongwen.gitbook.io/leetcode-report/medium/394.-decode-string.md).

# 394. Decode String

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".
```

#### 解题要点：

血汗的教训啊！这题如果忽略左口号，会很难办。所以，先把所有左括号前的字母加到res里，这时如果碰到右括号，就开始提取数字stack对字母stack和res进行计算，算完后继续放养，直到遇到下一个左括号，再把res里的字母加到字母stack里。这样可以保证格式一定工整，不会混淆左右括号的层次。

```python
class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        res = ""
        stNum = []
        stChar = []
        i = 0
        while i < len(s):
            if s[i].isdigit():
                num = int(s[i])
                while i+1 < len(s) and s[i+1].isdigit():
                    num = num * 10 + int(s[i+1])
                    i+=1
                stNum.append(num)
            elif s[i] == '[':
                stChar.append(res)
                res = ""
            elif s[i] == ']':
                tempNum = stNum.pop()
                tempChar = stChar.pop()

                while tempNum > 0:
                    tempChar += str(res)
                    tempNum -= 1
                res = tempChar
            else:
                res += str(s[i])
                
            i+=1
        return res
        
```