# 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[4]`.

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

Constraints:

• `1 <= s.length <= 30`
• `s` consists of lowercase English letters, digits, and square brackets `'[]'`.
• `s` is guaranteed to be a valid input.
• All the integers in `s` are in the range `[1, 300]`.

## Explanation

Using recursion to solve the problem. Whenever we see a left bracket ‘[‘, we use a helper function to build a substring repeating with the precedent number of times.

## Python Solution

``````class Solution:
def decodeString(self, s: str) -> str:
if not s:
return ""

result, position = self.helper(s, 0)

return result

def helper(self, s, position):
result = ""

number = 0

while position < len(s):
char = s[position]

if char.isdigit():
number = number * 10 + int(char)
elif char == '[':
substring, position = self.helper(s, position + 1)
result += substring * number
number = 0
elif char == ']':
return result, position
else:
result += char

position += 1

return result, position
``````
• Time Complexity: ~N
• Space Complexity: ~N

## One Thought to “LeetCode 394. Decode String”

1. Sudhir says:

It would be very halpful if you post a C programming code for the same question.