 # Decode String Leetcode

#1

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

Examples:

```s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
```

#2

We use a stack to track the digits and the values to append.

``````public class Solution {
public String decodeString(String s) {
if(s==null || s.length()==0) return "";
Stack<Integer> counts = new Stack<>();
Stack<StringBuilder> values = new Stack<>();
values.push(new StringBuilder());
int num = 0;
for(int i=0;i<s.length();i++){
char ch = s.charAt(i);
if(ch>='0' && ch<='9'){
num = num*10+ (ch-'0');
} else if(ch=='['){
values.push(new StringBuilder());
counts.push(num);
num = 0; //reset for next nums
} else if(ch==']'){
String toAppend = values.pop().toString();
int count = counts.pop();
StringBuilder nsb = new StringBuilder();
for(int j=0;j<count;j++){
nsb.append(toAppend);
}
values.push(values.pop().append(nsb.toString()));
}else{
values.peek().append(ch);
}
}

return values.pop().toString();
}
}
``````