字符串解码

本题是一道模拟题。

题目给定一个编码字符串 s，要求我们将其解码并返回解码后的字符串。

编码规则为：k[encoded_string] 表示将方括号内的 encoded_string 重复 k 次，其中 k 是正整数，encoded_string 是需要重复的字符串。编码字符串可以嵌套，即 encoded_string 内部还可以包含其他编码字符串。

例如：

3[a] 解码为 aaa。
2[abc] 解码为 abcabc。
3[a2[c]] 解码为 accaccacc。

此外，题目保证输入中的数字只表示重复次数 k，不会出现 3a 或 2[4] 这样的输入。

那么，我们应该如何解码这样的字符串呢？

对于不包含嵌套结构的编码字符串，例如 3[a]，我们只需要将方括号内的字符串 a 重复三次，就能得到解码结果 aaa。

然而，如果编码字符串包含嵌套结构，例如 3[a2[c]]，情况就有所不同了。

在这个例子中，内层的 2[c] 需要先解码为 cc，然后才能将外层的 3[a2[c]] 转换为 3[acc]，最终得到 accaccacc。

这说明，当编码字符串存在嵌套时，我们需要先完成内层的解码，再继续处理外层的编码结构。

以 3[a2[c]] 为例，处理内层的 2[c] 时，外层的重复次数 3 和已有字符串 a 还不能用于完成解码，需要等内层解码完成后，才能继续处理外层。

因此，处理内层结构时，我们需要暂存外层的信息，等内层解码完成后，再继续处理外层。

那么，外层具体需要暂存哪些信息呢？

仍以 3[a2[c]] 为例，在开始处理内层的 2[c] 时，我们需要暂存两项信息：

重复次数 3：内层解码完成后，需要将外层的解码结果重复三次。
已有字符串 a：内层解码完成后，需要将其解码结果拼接到 a 后面。

保存好这两项信息后，我们便可以独立处理内层结构，并在内层解码完成后，利用之前保存的信息继续处理外层。

那么，我们应该如何管理这些暂存的信息呢？

以 2[a3[b4[c]]] 为例，当我们开始处理最外层的 2[...] 时，已经知道重复次数为 2，但其中的字符串还没有解码完成。接下来遇到 3[...]，我们又需要暂时保留这一层的重复次数 3 和已有字符串 a；继续深入到 4[c] 时，也需要保存当前这一层的信息。

可以看到，随着解码过程不断深入，我们需要依次保存各层的信息。而解码时，需要先完成最内层，再逐层向外处理。因此，取出这些信息的顺序，应该与保存顺序相反。

这种信息管理方式恰好符合栈的后进先出特性：后保存的信息先取出，先保存的信息后取出。因此，我们可以使用栈来保存各层尚未处理完毕的信息。

这种暂存当前状态、处理内层问题、再恢复外层状态的过程，是不是与函数调用栈有些相似呢？

明确了使用栈保存外层信息后，我们再来看如何遍历字符串，并完成解码。

遍历过程中，我们需要维护两个状态：

repeatCount：记录当前正在解析的重复次数。
curString：记录当前正在构建的字符串。

然后，根据遍历到的字符类型，分别进行处理：

当遇到数字时，我们需要计算当前的重复次数。由于重复次数可能包含多位数字，因此需要逐位累积。
当遇到字母时，直接将其追加到 curString 中。
当遇到左方括号 [ 时，说明即将进入内层结构。此时，我们需要将当前的重复次数和已经构建好的字符串保存到栈中，然后重置这两个状态，以便独立处理内层字符串。
当遇到右方括号 ] 时，说明当前层的解码已经完成。此时，我们从栈中取出之前保存的外层信息，将当前字符串重复指定次数，并拼接到外层已有的字符串后面，得到新的当前字符串。

基于以上思路，我们可以写出以下代码：

▼
java
复制代码
public String decodeString(String s) {
    Deque<State> stack = new ArrayDeque<>();
    StringBuilder curString = new StringBuilder();
    int repeatCount = 0;

    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (Character.isDigit(c)) {
            repeatCount = repeatCount * 10 + (c - '0');
        } else if (Character.isLetter(c)) {
            curString.append(c);
        } else if (c == '[') {
            // 保存外层状态
            stack.push(new State(repeatCount, curString.toString()));
            // 重置状态，开始处理内层
            repeatCount = 0;
            curString.setLength(0);
        } else {
            // 取出外层状态
            State state = stack.pop();
            // 将内层解码结果重复指定次数，并拼接到外层字符串后面
            String innerString = curString.toString();
            curString.setLength(0);
            curString.append(state.outerString);
            for (int j = 0; j < state.repeatCount; j++) {
                curString.append(innerString);
            }
        }
    }
    return curString.toString();
}
static class State {
    int repeatCount;
    String outerString;

    public State(int repeatCount, String outerString) {
        this.repeatCount = repeatCount;
        this.outerString = outerString;
    }
}

本题也可以使用递归实现。有兴趣的读者可以尝试从递归的角度思考，如何处理嵌套的编码结构。

【栈模拟】字符串解码

字符串解码

目录

目录