题目描述

解题思路

辅助栈

使用2个栈，一个记录当前字符串出现的次数，也就是 [ 前的数字。一个记录当前字符串，还没遇到 ] 表示没有追加k的时候，遇到 ] 后按照 [ 前的数字进行追加，在入栈。

参照动图🔗

public String decodeString(String s) {
    int multi = 0;  // 表示括号中字符串出现次数
    StringBuilder res = new StringBuilder(); // 字符串结果
    Stack<String> stack_res = new Stack<>();
    Stack<Integer> stack_multi = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '[') {
            // 将次数入栈
            stack_multi.push(multi);
            // 重新赋值为0，防止后面的数字使用
            multi = 0;
            // res操作同理
            stack_res.push(res.toString());
            res = new StringBuilder();
        } else if (c == ']') {
            StringBuilder temp = new StringBuilder();
            Integer n = stack_multi.pop();
            for (int i = 0; i < n; i++) temp.append(res);
            res = new StringBuilder(stack_res.pop() + temp);
        }
        // 注意数字范围是1<=n<=300，所以multi需要乘10后再相加
        else if ('0' <= c && c <= '9') multi = multi * 10 + Integer.parseInt(c + "");
        else res.append(c);
    }
    return res.toString();
}

递归法

递归法算法思路和迭代法一致，递归从 [ 开始，从 ] 结束。
用一个队列来记录遍历的到达字符串s的什么地方，很方便的获取字符。而不用单独操作索引。

// 递归法
public String decodeString(String s) {
    Queue<Character> queue = new LinkedList<>();
    for (char c : s.toCharArray()) {
        queue.offer(c);
    }
    return dfs(queue);
}
public String dfs(Queue<Character> queue) {
    StringBuilder res = new StringBuilder();
    int multi = 0;
    while (!queue.isEmpty()) {
        char c = queue.poll();
        if (c == '[') {
            String tmp = dfs(queue);
            while (multi > 0) {
                res.append(tmp);
                multi--;
            }
        } else if (c == ']') {
            return res.toString();
        } else if ('0' <= c && c <= '9') multi = multi * 10 + Integer.parseInt(c + "");
        else res.append(c);
    }
    return res.toString();
}
}