# LeetCode 394. Decode String

## Description

https://leetcode.com/problems/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`.

Example 1:

```Input: s = "3[a]2[bc]"
Output: "aaabcbc"
```

Example 2:

```Input: s = "3[a2[c]]"
Output: "accaccacc"
```

Example 3:

```Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
```

Example 4:

```Input: s = "abc3[cd]xyz"
Output: "abccdcdcdxyz"```

using stack

## Python Solution

``````class Solution:
def decodeString(self, s: str) -> str:
stack = []

for c in s:
if c != ']':
stack.append(c)
continue

strs = []
while stack and stack[-1] != '[':
strs.append(stack.pop())

stack.pop()

repeats = 0
base = 1
while stack and stack[-1].isdigit():
repeats += (ord(stack.pop()) - ord('0')) * base
base *= 10
stack.append(''.join(reversed(strs)) * repeats)

return ''.join(stack)``````
• Time Complexity: ~N
• Space Complexity: ~N