建湖网页设计_常德网站建设案例教程_网站排名优化_什么是网站推广优化

问题背景

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

数据约束

• $1\le s.length\le 30$
• $s$ 由小写英文字母、数字和方括号 ‘[]’ 组成
• $s$ 保证是一个 有效 的输入
• $s$ 中所有整数的取值范围为 $[1,300]$

解题过程

这题标签是中等，但还是比较复杂的。
从一般的思路来说，它是一个从里到外的过程。
因为有可能出现嵌套使用 $k[encoded\_string]$ 这个规则的可能，所以有必将已经完成解析的字符串记录到栈中。
在这个基础上，遇到不同的字符进行相应的处理即可。

具体实现

class Solution {public String decodeString(String s) {// 定义两个栈，一个用来记录系数，一个用来记录已经完成解析的字符串Deque<Integer> integerStack = new ArrayDeque<>();Deque<String> stringStack = new ArrayDeque<>();int times = 0;StringBuilder stringBuilder = new StringBuilder();for(char c : s.toCharArray()) {// 在当前处理过程中，按数位顺序计算系数if(Character.isDigit(c)) {times = times * 10 + c - '0';}// 遇到左括号，将当前的字符串记录到栈中if(c == '[') {integerStack.push(times);times = 0;stringStack.push(stringBuilder.toString());stringBuilder.setLength(0);}// 遇到右括号，根据题意重复字符串，并对当前处理的字符串进行更新if(c == ']') {StringBuilder cur = new StringBuilder();int curTimes = integerStack.pop();for(int i = 0; i < curTimes; i++) {cur.append(stringBuilder);}stringBuilder = new StringBuilder(stringStack.pop() + cur);}// 在当前处理过程中，英文字母直接添加到末尾if(Character.isLetter(c)) {stringBuilder.append(c);}}return stringBuilder.toString();}
}