字符串解码

## 1 题目

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

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

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

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

**示例 1：**

```txt
输入：s = "3[a]2[bc]"
输出："aaabcbc"
```

**示例 2：**

```txt
输入：s = "3[a2[c]]"
输出："accaccacc"
```

**示例 3：**

```txt
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
```

**示例 4：**

```txt
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"
```

## 2 问题分析

1. **构建两个辅助栈 $lastMultiStack$**、$lastResStack$，**分别用于临时存放 `[` 前的遍历的倍数和结果**。
2. **遍历字符串 $s$ 中的每个字符 $c$**：

1. **当 $c$ 为数字时**：

1. **将数字字符转化为数字 $multi$**，**用于后续倍数计算**。

![](/media/202206/2022-06-07_153357_250179.png)
   2. **当 $c$ 为字母时**：

1. **在 $res$ 尾部添加 $c$**。

![](/media/202206/2022-06-07_153438_472342.png)
   3. **当 $c$ 为 `[` 时**：

1. **记录此 `[` 前的临时结果 $res$ 入栈**，**用于发现对应 `]` 后的拼接操作**。
      2. **记录此 `[` 前的倍数 $multi$ 入栈**，**用于发现对应 `]` 后**，**获取 $multi \times [\cdots]$ 字符串**。
      3. **将 $res$**、**$multi$ 分别置空置 0**。

![](/media/202206/2022-06-07_153504_034646.png)
   4. **当 $c$ 为 `]` 时**：

1. **$lastResStack$ 出栈**，**获取 $lastRes$**。
      2. **$lastMultiStack$ 出栈**，**获取 $currentMulti$**。
      3. **拼接字符串 $res = lastRes + currentMulti \times res$**。

![](/media/202206/2022-06-07_153534_738665.png)
3. **返回字符串 $res$**。

![](/media/202206/2022-06-07_153313_011567.gif)

## 3 参考代码

```java
/**
 * 394. 字符串解码
 * @param s 编码后的字符串
 * @return  解码后的字符串
 */
public String decodeString(String s) {
    //  最后结果
    StringBuilder res = new StringBuilder();
    //  数字栈
    LinkedList<Integer> lastMultiStack = new LinkedList<>();
    //  临时结果栈
    LinkedList<String> lastResStack = new LinkedList<>();
    //  临时数字
    int multi = 0;

for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '[') {
            /**
             * 如果当前字符为 [，则：
             *  1. 将当前 multi 和 res 入栈。
             *  2. 分别将 multi、res 置空置 0
             */
            lastMultiStack.addLast(multi);
            lastResStack.addLast(res.toString());
            multi = 0;
            res = new StringBuilder();
        } else if (c == ']') {
            /**
             * 如果当前字符为 ]，则：
             *  1. lastResStack 出栈，获取 lastRes。
             *  2. lastMultiStack 出栈，获取 currentMulti。
             *  3. res = lastRes + currentMulti * res
             */
            String lastRes = lastResStack.removeLast();
            StringBuilder tmp = new StringBuilder();
            int currentMulti = lastMultiStack.removeLast();
            for (int j = 0; j < currentMulti; j++) {tmp.append(res);}
            res = new StringBuilder(lastRes + tmp);
        } else if (c >= '0' && c <= '9') {
            /**
             * 如果当前字符为数字，则：
             *  1. 将数字字符转化为数字 multi
             */
            multi = multi * 10 + c - '0';
        }
        else {
            /**
             * 如果当前字符为字母，则：
             *  1. 在 res 尾部添加 c
             */
            res.append(c);
        }
    }
    //  返回最后的结果
    return res.toString();
}
```

## 参考文献

1. [394. 字符串解码](https://leetcode-cn.com/problems/decode-string)。
2. [字符串解码（辅助栈法 / 递归法，清晰图解）](https://leetcode-cn.com/problems/decode-string/solution/decode-string-fu-zhu-zhan-fa-di-gui-fa-by-jyd)。