【数据结构-字符串 三】【栈的应用】字符串解码

废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【字符串转换】，使用【字符串】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。

明确目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。

字符串解码【MID】

字符串和栈结合的一道题

题干

解题思路

原题解地址，本题难点在于括号内嵌套括号，需要从内向外生成与拼接字符串，这与栈的先入后出特性对应

算法流程：构建辅助栈 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。

返回字符串 res。

代码实现

给出代码实现基本档案

基本数据结构：字符串
辅助数据结构：无
算法：迭代
技巧：无

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param s string字符串* @param n int整型* @return string字符串*/public String decodeString(String s) {// 1 定义结果集、倍数、乘积栈和临时结果栈，以 3[a2[c]]为例StringBuilder res = new StringBuilder();int multi = 0;Stack<Integer> stack_multi = new Stack<Integer>();Stack<String> stack_res = new Stack<String>();// 2 遍历字符，依据不同的情况进行判断，字符串中只有4种字符，对应4种情况for (Character c : s.toCharArray()) {if (c == '[') {// 2-1 如果是左括号，则临时存储倍数和临时结果集用于后续拼接。并重置倍数和临时结果stack_multi.push(multi);stack_res.push(res.toString());multi = 0;res = new StringBuilder();} else if (c == ']') {// 2-2 如果是右括号StringBuilder tmp = new StringBuilder();// 弹出上个倍数并计算当前结果集：计算结果为：ccint cur_multi = stack_multi.pop();for (int i = 0; i < cur_multi; i++) {tmp.append(res);};// 与上个临时结果合并，计算结果为：accres = new StringBuilder(stack_res.pop() + tmp);} else if (c >= '0' && c <= '9') {// 2-3 如果是倍数，这里*10是因为要考虑重复次数大于10的情况，例如11multi = multi * 10 + Integer.parseInt(c + "");} else {// 2-4 如果是字符，直接放入结果集res.append(c);}}return res.toString();}
}

复杂度分析

时间复杂度 O(N)，一次遍历 s；
空间复杂度 O(N)，辅助栈在极端情况下需要线性空间，例如 2[2[2[a]]]。