LC394. 字符串解码

题目描述

给定一个经过编码的字符串，返回它解码后的字符串。 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。 示例 1： 输入：s = "3[a]2[bc]" 输出："aaabcbc" 示例 2： 输入：s = "3[a2[c]]" 输出："accaccacc" 示例 3： 输入：s = "2[abc]3[cd]ef" 输出："abcabccdcdcdef" 示例 4： 输入：s = "abc3[cd]xyz" 输出："abccdcdcdxyz" 提示： 1 <= s.length <= 30 s 由小写英文字母、数字和方括号 '[]' 组成 s 保证是一个 有效 的输入。 s 中所有整数的取值范围为 [1, 300]

题目解析

题目在说什么

这道题是让我们把一种“加密”的字符串还原成原来的样子。加密规则很简单：k[encoded_string] 表示方括号里的字符串要重复 k 次。比如 3[a] 就是 a 重复 3 次，变成 aaa。

但事情没那么简单，因为括号可以嵌套，比如 3[a2[c]]，意思是先算里面的 2[c] 得到 cc，再算外面的 3[acc] 得到 accaccacc。所以我们要一层一层地解开，就像剥洋葱一样。

思路是怎么来的

想象一下你在玩一个“套娃”游戏。你有一个大盒子，里面装着一些小盒子，小盒子里可能还有更小的盒子。你要把所有盒子都打开，把里面的东西拿出来，然后按照盒子上的数字重复放。

当你打开一个盒子（遇到 [）时，你需要记住两件事： 1. 这个盒子要重复几次（数字）。 2. 这个盒子外面已经有什么东西了（之前的字符串）。

然后你才能安心地去处理盒子里的内容。等处理完里面的内容（遇到 ]），你就要把刚才记住的重复次数和外面的东西拿出来，把里面的内容重复后拼接到外面。

这个过程特别像“栈”的工作方式：后进去的先出来。你最后打开的盒子（最内层）最先处理完，然后处理它的外层，再处理更外层。所以用栈来存储“外面的信息”非常合适。

代码逐步拆解

我们来看代码是怎么一步步实现这个思路的。

1. 准备两个栈

Deque<Integer> numStack = new LinkedList<>();
Deque<StringBuilder> strStack = new LinkedList<>();

• numStack：数字栈，用来存“重复次数”。比如遇到 3[ 时，就把 3 存进去。
• strStack：字符串栈，用来存“外面的字符串”。比如遇到 3[a2[c]] 时，处理到第一个 [ 时，外面还没有东西，就存一个空字符串；处理到第二个 [ 时，外面已经有 a 了，就把 a 存进去。

2. 准备两个变量

int digit = 0;
StringBuilder res = new StringBuilder();

• digit：用来记录当前遇到的数字。注意数字可能不止一位，比如 12[ab]，我们要把 1 和 2 拼成 12。
• res：用来存放当前已经解码好的字符串。一开始是空的，随着遍历慢慢增加。

3. 开始遍历字符串

for (int i = 0; i < s.length(); i++) {
    char ch = s.charAt(i);

对每个字符，分四种情况处理。

情况1：遇到数字

if (Character.isDigit(ch)) {
    int num = ch - '0';
    digit = digit * 10 + num;
}

• 把字符 '3' 转成数字 3，用 ch - '0' 就行。
• 如果之前已经有数字了（比如 digit 是 1），现在又遇到 2，就要拼成 12，所以 digit = digit * 10 + num。

情况2：遇到字母

else if ((ch >= 'a' && ch <= 'z')) {
    res.append(ch);
}

• 字母就是普通字符，直接加到当前结果 res 里。比如 abc 就直接变成 abc。

情况3：遇到 [

else if (ch == '[') {
    numStack.push(digit);
    strStack.push(res);
    digit = 0;
    res = new StringBuilder();
}

• 遇到 [ 表示要开始一个新“盒子”了。我们需要把当前的信息存起来：
• 把重复次数 digit 存到数字栈。
• 把当前已经解码好的字符串 res 存到字符串栈。
• 然后重置 digit 和 res，准备处理盒子里的内容。

情况4：遇到 ]

else if (ch == ']') {