Leetcode 394.字符串解码

Leetcode 算法栈

Leetcode

发布日期: 2023-09-09

更新日期: 2023-09-09

文章字数: 1.1k

阅读时长: 4 分

阅读次数:

Leetcode 394. 字符串解码

摘要：本题名为字符串的解码，实际上分为两部分，一部分是字符串出现的次数；另外一部分是子字符串。本题引入数据结构是栈，通过对"[ ]"括号的分类，判断入栈出栈的时机，对全部的字符串进行解码。

1. 题目说明

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：
```
输入：s = "3[a]2[bc]"
输出："aaabcbc"
```
示例 2：
```
输入：s = "3[a2[c]]"
输出："accaccacc"
```

2. 解答分析

一看到题目想到的是对数字和字符进行分类，但是后来考虑到这是通过字符串的形式进行的解码，而且对数字和字符串的匹配关系存在==“[ ]“的要求，所以这里就对”[ ]”==进行讨论，将引入辅助栈对数字和字符串进行匹配，算法的流程如下：
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。
其实就是对所有的字符进行划分，引入两个栈空间对数字和字符进行存储，这里要用到的是LinkedList的数据结构链表，对字符串进行拼接。

3. 具体代码

Java代码如下：

class Solution {
    public String decodeString(String s) {
        //首先需要注意的是对于字符串的拼接和次数的限制.这里还有‘[]’的要求，其实有提示就是需要栈的进出
        StringBuffer res=new StringBuffer();
        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;//对应的清0
                res=new StringBuffer();//res重置为空的字符串，便于后续的存储
            }
            else if(c==']'){
                StringBuffer tmp=new StringBuffer();//添加暂时的中间变量
                int cur_multi=stack_multi.removeLast();//弹出最后的元素，并且在弹出后首先清除
                for(int i=0;i<cur_multi;i++){
                    tmp.append(res);//遍历需要复写的次数
                }
                res=new StringBuffer(stack_res.removeLast()+tmp);//返回特定的字符串，为下一次遍历做准备
            }
            else if(c>='0' && c<='9'){
                multi=multi*10+Integer.parseInt(c+"");//先将字符'c'转化为字符串的形式，后来当遇到一个数字字符时，将其转换为整数，并将其累积到乘数中，让多个字符形成字符串的格式
            }
            else res.append(c);//字符串直接拼接
        }
        return res.toString();
    }
}