    public String decodeString(String s) {
        Stack<Integer> numStack = new Stack<>();
        Stack<String> strStack = new Stack<>();
        StringBuilder curStr = new StringBuilder();
        int num = 0;

        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            //1. 数字
            if(c >= '0' && c <= '9') {
                num = num * 10 + (c - '0');
            } else if(c == '[') {
                //2. 此时数字结束，curStr 也要结束
                numStack.push(num);
                strStack.push(curStr.toString());

                num = 0;
                curStr = new StringBuilder();
            } else if(c == ']') {
                //3. 此时需要重复的字符遍历结束
                String pre = strStack.pop();    // 原来的字符串
                int times = numStack.pop();
                StringBuilder temp = new StringBuilder(pre);

                for(int j = 0; j < times; j++) {
                    // 针对 [] 的字符串 repeat
                    temp.append(curStr);
                }
                curStr = temp;
            } else {
                curStr.append(c);
            }
        }    

        return curStr.toString();
    }

效果

1ms 击败 74.75%

反思

如何通过 dfs 来解决呢？

v2-递归

思路

用一个全局下标 i 遍历字符串。
定义一个函数 decode(s)：

从 i 开始，解析出一个子串。

如果遇到字母，直接拼接到结果。

如果遇到数字，解析出完整的数字 num，跳过 [，递归调用 decode(s) 得到括号里的子串。
然后重复 num 次拼接到结果里。

如果遇到 ]，说明当前层结束，返回结果。

外层调用 decode(s) 就能得到最终答案。

实现

某种角度而言，和 stack 很类似。只不过这个栈是系统帮我们隐式处理了而已

    private int i = 0; // 用于记录当前遍历到的位置

    public String decodeString(String s) {
        return helper(s);
    }

    // 递归函数：从当前位置开始解码，直到遇到 ']' 或字符串结尾
    private String helper(String s) {
        StringBuilder res = new StringBuilder();

        while (i < s.length() && s.charAt(i) != ']') {
            char c = s.charAt(i);

            // 1如果是字母，直接拼到结果里
            if (Character.isLetter(c)) {
                res.append(c);
                i++;
            }
            // 2如果是数字，说明接下来是 k[xxx] 的格式
            else if (Character.isDigit(c)) {
                int num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + (s.charAt(i) - '0'); // 处理多位数
                    i++;
                }

                i++; // 跳过 '['
                String sub = helper(s); // 递归解码括号里面的内容
                i++; // 跳过 ']'

                // 把 sub 重复 num 次拼接到结果
                for (int k = 0; k < num; k++) {
                    res.append(sub);
                }
            }
        }

        return res.toString();
    }

效果

0ms 100%

v3-BFS

思路

个人感觉BFS解决这一题不适合阅读，不太推荐。只是记录一下。

1）用队列 BFS 逐层展开字符串。

2）每次处理最外层的 k[xxx]：

找到数字 k

找到匹配的 [...]

将子串重复 k 次

拼接成新字符串，放回队列继续处理

3）队列为空时，说明字符串已经完全展开，返回结果。

实现

    public String decodeString(String s) {
        Queue<String> queue = new LinkedList<>();
        queue.offer(s);

        while (!queue.isEmpty()) {
            String curr = queue.poll();

            // 找到最外层的 k[xxx] 模式
            int start = curr.indexOf('[');
            if (start == -1) {
                // 没有 '['，说明已经完全展开
                return curr;
            }

            int numStart = start - 1;
            while (numStart >= 0 && Character.isDigit(curr.charAt(numStart))) {
                numStart--;
            }
            numStart++; // k 的起始位置

            int repeat = Integer.parseInt(curr.substring(numStart, start));

            // 找到匹配的 ']'
            int end = start;
            int count = 1;
            while (count > 0) {
                end++;
                char c = curr.charAt(end);
                if (c == '[') count++;
                if (c == ']') count--;
            }

            String sub = curr.substring(start + 1, end); // 子串
            String repeated = sub.repeat(repeat);       // 重复 k 次

            // 拼接生成新字符串，并放回队列继续处理
            String next = curr.substring(0, numStart) + repeated + curr.substring(end + 1);
            queue.offer(next);
        }

        return "";
    }

耗时

8ms 10.95%

开源项目

为方便大家学习，所有相关文档和代码均已开源。

leetcode-visual 资源可视化

leetcode 算法实现源码

leetcode 刷题学习笔记

老马技术博客

小结

希望本文对你有帮助，如果有其他想法的话，也可以评论区和大家分享哦。

各位极客的点赞收藏转发，是老马持续写作的最大动力！

下一节我们将讲解力扣经典，感兴趣的小伙伴可以关注一波，精彩内容，不容错过。

贡献者

bbhou