394 字符串解码

一、题目

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

测试用例保证输出的长度不会超过 10^5。

二、题解

思路：双栈法

在遍历字符串的过程中，我们需要维护两个核心状态：

  1. res (当前拼接的字符串)：记录当前层级已经解析出的字母。
  2. multi (当前的倍数)：记录当前层级遇到的数字。

同时，我们需要准备两个栈来保存上一层的状态：

  • stack_multi (数字栈)：用来记录遇到 [ 之前的倍数。
  • stack_res (字符串栈)：用来记录遇到 [ 之前已经拼接好的字符串。

遍历字符串时，有以下四种情况：

  1. 遇到数字 ('0'-'9')： 需要考虑数字可能是多位数（比如 "100[a]"），所以更新当前的倍数：multi = multi * 10 + 当前数字。
  2. 遇到字母 ('a'-'z' 或 'A'-'Z')： 直接追加到当前的字符串 res 后面。
  3. 遇到左括号 [： 这意味着要进入更深一层的嵌套了。我们需要把外层的状态（当前的 multi 和 res）压入各自的栈中保存起来。 入栈后，将当前的 multi 重置为 00，res 清空，准备开始记录内层括号里的新数字和新字母。
  4. 遇到右括号 ]： 内层括号的内容处理完了，需要和外层拼接。
    • 从 stack_multi 弹出一个倍数 k。
    • 将当前的 res 重复 k 次。
    • 从 stack_res 弹出一个字符串 last_res（这是外层之前已经拼好的部分）。
    • 将重复 k 次后的新字符串，拼接到 last_res 的后面，更新为当前的 res。
import java.util.LinkedList;

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(); // 弹出倍数
                // 将当前层的 res 重复 cur_multi 次
                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
                res.append(c);
            }
        }
        return res.toString();
    }
}

时间复杂度：O(N)O(N)

空间复杂度：O(M)O(M)

评论