# 394. Decode String

[ **394. Decode String**](https://leetcode.com/problems/decode-string/description/)

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

***My Solutions：***

用两个stack，分别储存StringBuilder(用来组成字母）和数字。用一个StringBuilder res保存结果，用一个int num保存当前数字。

在依次检查input里的每一个char时，根据char做如下判断：

* 如果char是一个数字
  * 如果num是0，把之前的res存入string stack
  * 计算新的num值: num = 10 \* num + c - '0'; 这一步的是为了算数字，比如32就是三十二
* 如果char是【，把之前存下来的数字存入数字stack中，重置num，重置res，因为将要有新的字母组合
* 如果char是一个字母，把字母append到res上
* 如果char是】，取出string stack里的stringbuilder top，取出int stack里的数字n。把res append到top上n次。给res赋值top

举个例子“3\[a2\[c]]”：

* 3：string stack里加入一个空的stringbuilder;num=3
* 【： int stack里加入3；num=0; res=new StringBuilder;
* a：res="a";
* 2：string stack里加入"a"; num = 2
* 【：int stack里加入2；num=0, res=new StringBuilder
* c：res="c";
* 】：top=“a”; n=2; res变成“acc”
* 】：top=""; n = 3; res变成“accaccacc”

```java
class Solution {
    public String decodeString(String s) {
        Stack<Integer> counters = new Stack<>();
        Stack<StringBuilder> strings = new Stack<>();

        StringBuilder res = new StringBuilder();
        int num = 0;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            if (Character.isDigit(c)) {
                if (num == 0) strings.push(res); //把之前的结果先存入string stack
                num = 10 * num + c - '0';
                
            } else if (c == '[') {
                counters.push(num); //把【之前的数字存入数字stack
                num = 0; //重置num
                res = new StringBuilder(); 
                
            } else if (Character.isLetter(c)) {
                res.append(c);
                
            } else if (c == ']') {
                StringBuilder top = strings.pop(); //top是之前存入在string stack里的char
                int n = counters.pop(); //n是此【】里需要循环的次数
                while (n-- != 0) top.append(res); //res是此【】里的char
                res = top;
            }
        }
        return res.toString();
    }
}
```