Java实现数字标注重复次数的嵌套括号字符串解码算法

规则说明 #

嵌套括号编码字符串通用形式为n[Am[b]]，编码规则：

• 数字代表其对应方括号内部字符串的重复次数
• 括号支持多层嵌套结构

测试样例 #

给定编码输入：

2[a]2[ab]
3[a]2[r2[t]]
a2[aa3[b]]

对应解码输出：

aaabab
aaarttrtt
aaabbbaabbb

Java实现方案 #

实现思路 #

嵌套结构天然适合用栈处理，这里用两个双端队列模拟栈结构：

• 一个栈存储待重复的次数，处理多层嵌套时的计数暂存
• 一个栈存储外层已经拼接完成的字符串，处理完内层括号后直接和外层结果拼接
  遍历字符串时按字符类型分情况处理：

1. 遇到数字：连续读取拼接成完整整数（兼容多位数字，比如12[a]代表a重复12次），暂存为当前重复次数
2. 遇到左括号[：将当前暂存的重复次数、当前已拼接的字符串分别压入对应栈，重置临时计数和当前拼接字符串
3. 遇到右括号]：弹出栈顶的重复次数、栈顶的外层历史字符串，将当前拼接的内层字符串按次数重复后，追加到外层历史字符串末尾，更新为当前拼接字符串
4. 遇到普通字母：直接追加到当前拼接字符串末尾

完整代码 #

import java.util.Deque;
import java.util.LinkedList;

public class NestedStringDecoder {
    public static String decode(String encodedStr) {
        Deque<Integer> countStack = new LinkedList<>();
        Deque<StringBuilder> contentStack = new LinkedList<>();
        StringBuilder currentContent = new StringBuilder();
        int currentCount = 0;

        for (char c : encodedStr.toCharArray()) {
            if (Character.isDigit(c)) {
                // 处理多位数字场景
                currentCount = currentCount * 10 + (c - '0');
            } else if (c == '[') {
                countStack.push(currentCount);
                contentStack.push(currentContent);
                currentCount = 0;
                currentContent = new StringBuilder();
            } else if (c == ']') {
                int repeat = countStack.pop();
                StringBuilder outerContent = contentStack.pop();
                // 重复拼接内层内容
                for (int i = 0; i < repeat; i++) {
                    outerContent.append(currentContent);
                }
                currentContent = outerContent;
            } else {
                currentContent.append(c);
            }
        }
        return currentContent.toString();
    }

    public static void main(String[] args) {
        String[] testInputs = {"2[a]2[ab]", "3[a]2[r2[t]]", "a2[aa3[b]]"};
        for (String input : testInputs) {
            System.out.println(decode(input));
        }
    }
}

运行结果 #

执行main方法可得到和预期一致的解码结果：

aaabab
aaarttrtt
aaabbbaabbb

内容的提问来源于stack exchange，提问作者VIctor