【LeetCode】【算法】394. 字符串解码

LeetCode 394. 字符串解码

题目描述

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

思路

思路：参考的题解字符串解码（辅助栈法 / 递归法，清晰图解）
在这个题解中的变量包括res临时存储字符串，multi临时存储数值，stack_multi作为辅助栈存储数值，stack_res作为辅助栈存储字符串，在这个算法中，规则为：

1. 假如遇到了数字，更新multi=10*multi+Integer.parse(c+””);
2. 假如遇到了字符，更新res=res.append(c)
3. 假如遇到了[，将multi和res中的内容入栈：multi.push(multi), res.push(res)并做清空multi=0, res=new StringBuilder()
4. 假如遇到了]，将stack_multi和stack_res中的内容出栈，得到目前的结果写入res中。实际上就是res=last_res+last_multi*res，即有：
   I. Integer m = stack_multi.pop(); String r = stack_res.pop()
   II. 根据值m和当前res中的内容，利用for循环组成字符串for(int i=0;i<m;i++) tmp.append(res)
   III. res=r+tmp

代码

class Solution {public String decodeString(String s) {StringBuilder res = new StringBuilder();int multi = 0;// 两个辅助栈，一个存数字，一个存字符串Deque<Integer> stack_multi = new ArrayDeque<>();Deque<String> stack_res = new ArrayDeque<>();for (char c : s.toCharArray()) {if (c == '['){ // 如果等于左括号，将res和multi入栈中stack_multi.push(multi);stack_res.push(res.toString());multi = 0;res = new StringBuilder();} else if (c == ']') { // 如果等于右括号，当前结果=last_res+last_multi*resInteger last_multi = stack_multi.pop();String last_res = stack_res.pop();StringBuilder tmp = new StringBuilder();for (int i = 0; i < last_multi; i++) tmp.append(res);res = new StringBuilder(last_res + tmp);}else if (c >= '0' && c <= '9') multi = multi * 10 + Integer.parseInt(c + "");else res.append(c);}return res.toString();}
}