## Algorithm

Problem Name: 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; there are 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 will not be input like `3a` or `2[4]`.

The test cases are generated so that the length of the output will never exceed `105`.

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

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

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
struct node {
int repeat;
};

char* decodeString(char* s) {
struct node stack[100], *p;
int sp = 0;

int n;

char *buff;
int sz, len;

char *newbuff = NULL;
int newsz, newlen;

buff = NULL;
sz = len = 0;
n = 0;
while (*s) {
if (*s == '[') {
p = &stack[sp ++];  // push and save

buff = NULL;
sz = len = 0;

p->repeat = n;
n = 0;
} else if (*s == ']') {
p = &stack[-- sp];  // pop and expand

newlen = p->leading_len + p->repeat * len;
newsz = newlen + 10;
newbuff = realloc(p->leading_string, newsz * sizeof(char));
//assert(newbuff);
newbuff[0] = 0;
}
while (p->repeat) {
strcat(newbuff, buff);
p->repeat --;
}
free(buff);
sz = newsz;
len = newlen;
buff = newbuff;
} else if (*s >= '0' && *s  < = '9') {
n = n * 10 + (*s) - '0';
} else {
if (len + 1 >= sz) {
if (sz == 0) sz = 10;
else sz *= 2;
buff = realloc(buff, sz * sizeof(char));
//assert(buff);
}
buff[len ++] = *s;
buff[len] = 0; // null terminated
}
s ++;
}
if (!buff) buff = calloc(1, sizeof(char));
//assert(buff);
return buff;
}
``````
Copy The Code &

Input

cmd
s = "3[a]2[bc]"

Output

cmd
"aaabcbc"

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
string decodeString(string s) {
if(s.empty()) return "";
string res = "";
int i = 0, j = 0;
while(j < s.size()){
while(j  <  s.size() && isalpha(s[j])) j++;
res += s.substr(i, j - i);
i = j;
if(j == s.size()) break;
while(isdigit(s[j])) j++;
int k = stoi(s.substr(i, j - i));
int cnt = 1;
i = j + 1;
while(cnt != 0)
if(s[++j] == ']') cnt--;
else if(s[j] == '[') cnt++;
while(k--) res += decodeString(s.substr(i, j - i)>;
i = ++j;
}
return res;
}
};
``````
Copy The Code &

Input

cmd
s = "3[a]2[bc]"

Output

cmd
"aaabcbc"

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public String decodeString(String s) {
Stack stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == ']') {
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty() && stack.peek() != '[') {
sb.append(stack.pop());
}
stack.pop();
String temp = sb.toString();
sb.setLength(0);
while (!stack.isEmpty() && Character.isDigit(stack.peek())) {
sb.append(stack.pop());
}
int count = Integer.parseInt(sb.reverse().toString());
while (count-- > 0) {
for (int i = temp.length() - 1; i >= 0; i--) {
stack.push(temp.charAt(i));
}
}
} else {
stack.push(c);
}
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.reverse().toString();
}
}
``````
Copy The Code &

Input

cmd
s = "3[a2[c]]"

Output

cmd
"accaccacc"

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const decodeString = function(s) {
const repeated = [];
const sbStack = [];

let mul = 0;
let sb = "";
for (let i = 0; i  <  s.length; i++) {
const c = s.charAt(i);
if (isDigit(c)) {
if (mul === 0) sbStack.push(sb); // here is the trick
mul = mul * 10 + +c;
} else if (c === "[") {
repeated.push(mul);
mul = 0;
sb = "";
} else if (isLetter(c)) {
sb += c;
} else if (c === "]") {
let top = sbStack.pop();
let r = repeated.pop();
while (r-- > 0) top += sb;
sb = top;
}
}

return sb;
};

function isDigit(c) {
return c.charCodeAt(0) >= 48 && c.charCodeAt(0)  < = 57;
}

function isLetter(c) {
return (
(c.charCodeAt(0) >= 65 && c.charCodeAt(0) <= 90) ||
(c.charCodeAt(0) >= 97 && c.charCodeAt(0) <= 122)
);
}
``````
Copy The Code &

Input

cmd
s = "3[a2[c]]"

Output

cmd
"accaccacc"

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def decodeString(self, s):
stack, num, string = [], 0, ""
for c in s:
if c == "[":
stack += string,
stack += num,
num, string = 0, ""
elif c == "]":
pre_num, pre_string = stack.pop(), stack.pop()
string = pre_string + pre_num * string
elif c.isdigit(): num = num * 10 + int(c)
else: string += c
return string
``````
Copy The Code &

Input

cmd
s = "2[abc]3[cd]ef"

Output

cmd
"abcabccdcdcdef"

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;
using System.Text;

namespace LeetCode
{
public class _0394_DecodeString
{
public string DecodeString(string s)
{
var countStack = new Stack < int>();
var strStack = new Stack();

var sb = new StringBuilder();
var num = 0;
foreach (var ch in s)
{
if (char.IsDigit(ch))
num = num * 10 + ch - '0';
else if (ch == '[')
{
strStack.Push(sb.ToString());
countStack.Push(num);
sb.Clear();
num = 0;
}
else if (ch == ']')
{
var str = sb.ToString();
sb.Clear();
sb.Append(strStack.Pop());

var count = countStack.Pop();
for (int i = 0; i  <  count; i++)
sb.Append(str);
}
else
sb.Append(ch);
}

return sb.ToString();
}
}
}
``````
Copy The Code &

Input

cmd
s = "2[abc]3[cd]ef"

Output

cmd
"abcabccdcdcdef"