# 394. Decode String (Medium)

https://leetcode.com/problems/decode-string/

Given an encoded string, return it's 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".
```

## Solutions

``````class Solution {

public String decodeString(String s) {
if (s == null || s.length() == 0) {
return s;
}

Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);

if (c != ']') {
stack.push(c);

continue;
}

// c == ']'

String pattern = "";

// pop out elements in []
while (stack.peek() != '[') {
pattern = stack.pop() + pattern;
}

// drop '['
stack.pop();

String multiple = "";

// retrieve the repeating times
while (!stack.isEmpty() && stack.peek() >= '0' && stack.peek() <= '9') {
multiple = stack.pop() + multiple;
}

// push in the repeated result string
String tmp = repeat(pattern, multiple);
for (char x : tmp.toCharArray()) {
stack.push(x);
}
}

String ans = "";
while (!stack.isEmpty()) {
ans = stack.pop() + ans;
}

return ans;
}

private String repeat(String pattern, String n) {
String ans = "";

if (n == null || n.length() == 0) {
return ans;
}

for (int i = 0; i < Integer.valueOf(n); i++) {
ans += pattern;
}

return ans;
}
}
``````

## Incorrect Solutions

``````class Solution {

// Incorrect solution, the bracket can be nested.

public String decodeString(String s) {
if (s == null || s.length() == 0) {
return s;
}

Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);

if (c != ']') {
stack.push(c);

continue;
}

// c == ']'

String pattern = "";

// pop out elements in []
while (stack.peek() != '[') {
pattern = stack.pop() + pattern;
}

// drop '['
stack.pop();

String multiple = "";

// retrieve the repeating times
while (!stack.isEmpty() && stack.peek() >= '0' && stack.peek() <= '9') {
multiple = stack.pop() + multiple;
}

// push in the repeated result string
String tmp = repeat(pattern, multiple);
for (char x : tmp.toCharArray()) {
stack.push(x);
}
}

String ans = "";
while (!stack.isEmpty()) {
ans = stack.pop() + ans;
}

return ans;
}

private String repeat(String pattern, String n) {
String ans = "";

if (n == null || n.length() == 0) {
return ans;
}

for (int i = 0; i < Integer.valueOf(n); i++) {
ans += pattern;
}

return ans;
}
}
``````