394. 字符串解码（高频题）

清疚 2023-10-04 08:49 49阅读 0赞

#### 394. 字符串解码 ####

*  解题思路
 *  代码

## 解题思路 ##

这题主要用到了**栈**，本题难点在于括号内嵌套括号，需要从内向外生成与拼接字符串，这与栈的先入后出特性对应。

**算法流程**  
1、构建辅助栈 stack， 遍历字符串 s 中每个字符 c；

*  当 c 为数字时，将数字字符转化为数字 multi，用于后续倍数计算；
 *  当 c 为字母时，在 res 尾部添加 c；
 *  当 c 为 \[ 时，将当前 multi 和 res 入栈，并分别置空置 0：
    
     *  记录此 \[ 前的临时结果 res 至栈，用于发现对应 \] 后的拼接操作；
     *  记录此 \[ 前的倍数 multi 至栈，用于发现对应 \] 后，获取 multi × \[…\] 字符串。
     *  进入到新 \[ 后，res 和 multi 重新记录。
 *  当 c 为 \] 时，stack 出栈，拼接字符串 `res = last_res + cur_multi * res`，其中:  
    `last_res`是上个 \[ 到当前 \[ 的字符串，例如 “3\[a2\[c\]\]” 中的 a；  
    `cur_multi`是当前 \[ 到 \] 内字符串的重复倍数，例如 “3\[a2\[c\]\]” 中的 2。

2、返回字符串 res。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 4]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 7]

## 代码 ##

class Solution {
        
        public String decodeString(String s) {
        
            StringBuilder res = new StringBuilder();
            int multi = 0;
            Stack<Integer> stack_multi = new Stack<>();
            Stack<String> stack_res = new Stack<>();
    
            for (Character c : s.toCharArray()) {
        
                if (c == '[') {
        
    //                当前 multi 和 res 入栈,并且把原来的multi和res置为0、null
                    stack_multi.push(multi);
                    stack_res.push(res.toString());
                    multi = 0;
                    res = new StringBuilder();
                } else if (c == ']') {
        
    //                stack 出栈，拼接字符串 res = last_res + cur_multi * res
                    StringBuilder tmp = new StringBuilder();
                    int cur_multi = stack_multi.pop();
                    for (int i = 0; i < cur_multi; i++) {
        
                        tmp.append(res);
                    }
                    res = new StringBuilder(stack_res.pop() + tmp);
                } else if (c >= '0' && c <= '9') {
        
    //                当 c 为数字时，将数字字符转化为数字 multi，用于后续倍数计算；
    //这里*10 是为了应对连续数字的情况。
                    multi = multi * 10 + Integer.parseInt(c + "");
                } else {
        
    //                当 c 为字母时，在 res 尾部添加 c；
                    res.append(c);
                }
            }
            return res.toString();
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210320102439729.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210320102445356.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210320102456897.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210320102503399.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20210320102511737.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20210320102516718.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20210320102520924.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20210320102525733.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70