394.字符串解码.md

方法一：栈

对字符串进行遍历扫描，每个字符 c 中有以下四种情况：

• c 是 '['，这时应该将multi和res压入栈中保存，同时将multi和res分别置零和置空
  • res有两个用途，一个是作为局部（每个[之前的结果）或者全局结果；另一个是记录[...]内的字符
• c 是 ']'，res正好记录的是[...]之内的字符结果，将数栈pop出结果进行叠加，例如 23[ab]，此时res记录的就是ab，然后将数栈中的23弹出进行结果的构建
• c 是数字，multi = multi * 10 + Integer.parseInt(c + "")，因为可能是23[ab]
• c 是字符，添加到res中，比如cd23[ab]，一开始res是cd，数是23，遇到 [ 将cd、23压入栈，再往后走res就是ab

class Solution {
    public String decodeString(String s) {
        StringBuilder res = new StringBuilder();
        int multi = 0;
        LinkedList<Integer> stack_multi = new LinkedList<>();
        LinkedList<String> stack_res = new LinkedList<>();
        for(Character c : s.toCharArray()) {
            if(c == '[') {
                stack_multi.addLast(multi);
                stack_res.addLast(res.toString());
                multi = 0;
                res = new StringBuilder();
            }
            else if(c == ']') {
                StringBuilder tmp = new StringBuilder();
                int cur_multi = stack_multi.removeLast();
                for(int i = 0; i < cur_multi; i++) tmp.append(res);
                res = new StringBuilder(stack_res.removeLast() + tmp);
            }
            else if(c >= '0' && c <= '9') multi = multi * 10 + Integer.parseInt(c + "");
            else res.append(c);
        }
        return res.toString();
    }
}