# 0394. Decode String
###### tags: `Leetcode` `Medium` `Stack`
Link: https://leetcode.com/problems/decode-string/
## 思路 $O(maxK*n)$ $O(n)$
用双栈 一个存数字 一个存StringBuilder
存StringBuilder的原因是每个放进去的字符串都有可能需要继续往后面加
拿到一个[, 重新记录数字和currString
拿到一个]，把上一个存进stack的字串pop出来，加上k（从number stack里面pop出来）个currStr（还没存进stack的str）
（currStr就是被当前的[]包着的字串，需要重复k遍，而且前面还需要加上上一层的[]里，出现在currStr左边的字串）
也就是如果是 3[ab2[c]]，读到第一个]的时候，需要先从stack里面把ab拿出来，因为ab村成了一个StringBuilder，直接在这个StringBuilder后面加上两个c，然后把现在的string当作currStr，因为只有遇到[的时候，代表重复的次数可能和之前不同，才需要放到Stack里面

这种题目的套路基本相同
如果cnt是1就自动省略 并且有层级 外面有cnt
那么我们需要先给str加一个空字符串 然后进行上面一系列操作
类似的还有**726.Number of Atoms**

## Code

class Solution {
    public String decodeString(String s) {
        StringBuilder curr = new StringBuilder();
        Stack<Integer> cnt = new Stack<>();
        Stack<StringBuilder> str = new Stack<>();
        int num = 0;
        for(int i=0; i<s.length(); i++){
            char c = s.charAt(i);
            if(Character.isDigit(c)){
                int j = i;
                while(j<s.length() && Character.isDigit(s.charAt(j))){
                    j++;
                }
                num = Integer.valueOf(s.substring(i, j));
                i = j-1;
            }
            else if(c=='['){
                cnt.add(num);
                num = 0;
                str.add(curr);
                curr = new StringBuilder();
            }
            else if(c==']'){
                StringBuilder prev = str.pop();
                for (int k = cnt.pop(); k > 0; k--) {
                    prev.append(curr);
                }
                curr = prev;
            }
            else curr.append(c);
        }
        return curr.toString();
    }
}