JAVA练习344- 字符串解码

题目概览给定一个经过编码的字符串返回它解码后的字符串。编码规则为:k[encoded_string]表示其中方括号内部的encoded_string正好重复k次。注意k保证为正整数。你可以认为输入字符串总是有效的输入字符串中没有额外的空格且输入的方括号总是符合格式要求的。此外你可以认为原始数据不包含数字所有的数字只表示重复的次数k例如不会出现像3a或2[4]的输入。测试用例保证输出的长度不会超过105。示例 1输入s 3[a]2[bc]输出aaabcbc示例 2输入s 3[a2[c]]输出accaccacc示例 3输入s 2[abc]3[cd]ef输出abcabccdcdcdef示例 4输入s abc3[cd]xyz输出abccdcdcdxyz提示1 s.length 30s由小写英文字母、数字和方括号[]组成s保证是一个有效的输入。s中所有整数的取值范围为[1, 300]来源394. 字符串解码 - 力扣LeetCode解题分析方法辅助栈难点在于括号内嵌套括号的情况我们可以定义辅助栈来存储 数字 和 数字前的字符串用 num 临时存储数字用 res 来存储结果遍历字符串当字符为数字时与当前数字做拼接 即 num num * 10 num当字符为字母时往 res 里添加当字符为左括号时将当前数字 num 和 数字后的字符串 res 入栈并将 num 置零res 置空当字符为右括号时出栈数字和字符串将 res * num 后拼接在 字符串 后面置空 res 并放入拼接后的字符串时间复杂度O(n)空间复杂度O(n)class Solution { public String decodeString(String s) { StringBuilder res new StringBuilder(); int num 0; DequeInteger numStack new LinkedList(); DequeString letterStack new LinkedList(); for (char c: s.toCharArray()) { if (c 0 c 9) { num num * 10 (c - 0); continue; } if (c [) { numStack.push(num); letterStack.push(res.toString()); num 0; res new StringBuilder(); continue; } if (c ]) { int num2 numStack.pop(); String letter letterStack.pop(); StringBuilder temp new StringBuilder(); while(num2-- 0) { temp.append(res.toString()); } res new StringBuilder(); res.append(letter); res.append(temp.toString()); continue; } res.append(c); } return res.toString(); } }