# Decode String

Posted on January 08, 2017

### 题目

Given an encoded string, return it’s decoded string.

The encoding rule is: $k[\text{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".


### 解法

public class Solution {
public String decodeString(String s) {
StringBuilder tmp = new StringBuilder();

int cnt = 0;

for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (Character.isDigit(ch)) {
cnt *= 10;
cnt += ch - '0';
} else if (ch == '[') {
digits.push(cnt);
tokens.push(new StringBuilder(tmp));
cnt = 0;
tmp.setLength(0);
} else if (ch == ']') {
int k = digits.pop();
while (k-- > 0) {
tokens.peek().append(tmp);
}
tmp = tokens.pop();
} else {
tmp.append(ch);
}
}