LeetCode 394：字符串解码
一、题目描述
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 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]
二、思路分析
注意示例 2 ，发现字符串中存在括号内有嵌套括号的情况，这个时候，只有先把内层括号解码成功，才能再去解码外层括号。意味着后面访问的括号比前面访问的括号还更早的进行处理，与栈的先入后出特点对应。所以本题可以使用栈的方式来进行解答。
1、构建两个栈，一个是数字栈 numStack ，在遍历字符串过程中记录出现的数字；一个是字符串栈 strStack ，在遍历字符串过程中记录出现的字符串。
2、初始化两个变量，一个是 digit ，用来记录访问到字符串之前出现的数字；一个是 result ，在访问编码字符串的过程中，把得到的结果存放到 result 中。
3、接下来，开始从头到尾遍历字符串，在遍历过程中，字符会出现 4 种情况，即数字、字符、"["、"]" 。
4、如果是数字，需要把字符转成整型数字，然后更新到 digit 上，代表后续的字符串需要重复 digit 次。
5、如果是字符，说明它就出现一次，可以直接存放到 result 中。
6、如果是 "[" ，这个时候出现了嵌套的内层编码字符串，而外层的解码需要等待内层解码的结果，那么之前已经扫描的字符需要存放起来，等到内层解码之后再重新使用。
7、如果是 "]" ，此时，内层解码已经有结果，需要把它和前面的字符串进行拼接。
8、拼接的方式就是先通过 numsStack 的栈顶元素获取重复的次数，再通过 strStack 的栈顶元素获取前面的字符串。
9、最后返回 result 。
三、代码参考
1、Java
class Solution {public String decodeString(String s) {// 创建数字栈，在遍历编码字符串过程中记录出现的数字Deque<Integer> numStack = new LinkedList<>();// 创建字符栈，在遍历编码字符串过程中记录出现的字符串Deque<StringBuilder> strStack = new LinkedList<>();// 在遍历字符串的过程中，用来记录访问到字符串之前出现的数字，一开始为 0int digit = 0;// 在遍历字符串的过程中，把得到的结果存放到 result 中StringBuilder result = new StringBuilder();// 循环遍历for (int i = 0; i < s.length(); i++) {// 获取访问的字符char ch = s.charAt(i);// 判断是否为数字字符if (Character.isDigit(ch)) {// 将字符转成整型数字 ch-‘0’// 补充：将字符'0'-'9'转换为数字，只需将字符变量减去'0'就行，因为字符和数字在内存里都是以 ASCII 码形式存储的，减去 '0' ，其实就是减去字符 '0' 的 ASCII 码，而字符 '0' 的 ASCII 码是 30，然后就可以得到字符对应的数字了int num = ch - '0';// 根据提示可知整数的取值范围是三位数，所以存在多位数，需要需要进行数字组合digit = digit * 10 + num ;}// 判断是否是字符else if((ch >= 'a' && ch <= 'z') ){// 说明它就出现一次，可以直接存放到 result 中result.append(ch);}// 判断是否是 "[" else if (ch == '[') {// 把数字存放到数字栈numStack.push(digit);// 把外层的解码字符串存放到字符串栈strStack.push(result);// 开始新的一轮解码，digit 归零digit = 0;// result 重新初始化result = new StringBuilder();}// 判断是否是"]" else if (ch == ']') {// 通过数字栈获取次数int count = numStack.poll();// 通过字符串栈获取之前的解码字符串StringBuilder outString = strStack.poll();// 循环把内层解码的字符串拼接起来for (int j = 0; j < count; j++) {// 拼接到 outString 后面，拼接 count 次outString.append(result.toString());}// 再把得到的结果赋值给 resultresult = outString;}}// 返回结果return result.toString();}
}2、Python
class Solution(object):def decodeString(self, s):# 创建数字栈，在遍历编码字符串过程中记录出现的数字numStack = []# 创建字符栈，在遍历编码字符串过程中记录出现的字符串strStack = []# 在遍历字符串的过程中，用来记录访问到字符串之前出现的数字，一开始为 0digit = 0# 在遍历字符串的过程中，把得到的结果存放到 result 中result = ""# 循环遍历for ch in s:# 判断是否为数字字符if '0' <= ch <= '9':# 将字符转成整型数字num = int(ch)# 根据提示可知整数的取值范围是三位数，所以存在多位数，需要需要进行数字组合digit = digit * 10 + num # 判断是否是字符elif ch >= 'a' and ch <= 'z':# 说明它就出现一次，可以直接存放到 result 中result += ch# 判断是否是 "[" elif ch == '[' :# 把数字存放到数字栈numStack.append(digit)# 把外层的解码字符串存放到字符串栈strStack.append(result)# 开始新的一轮解码，digit 归零digit = 0# result 重新初始化result = ""# 判断是否是"]" elif ch == ']':# 通过数字栈获取次数count = numStack.pop()# 通过字符串栈获取之前的解码字符串outString = strStack.pop()# 循环把内层解码的字符串拼接起来for j in range(0,count) : # 拼接到 outString 后面，拼接 count 次outString += result# 再把得到的结果赋值给 resultresult = outString# 返回结果return result