【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 <= 30
• s 由小写英文字母、数字和方括号 '[]' 组成
• s 保证是一个 有效 的输入。
• s 中所有整数的取值范围为 [1, 300] 

代码实现：

class Solution {  
    public String decodeString(String s) {  
        // 用于构建最终的解码字符串  
        StringBuilder res = new StringBuilder();  
          
        // 当前累积的重复次数  
        int multi = 0;  
          
        // 存储重复次数的栈，用于处理嵌套的情况  
        LinkedList<Integer> stack_multi = new LinkedList<>();  
          
        // 存储部分解码结果的栈，用于处理嵌套的情况  
        LinkedList<String> stack_res = new LinkedList<>();  
          
        // 遍历输入字符串的每个字符  
        for(Character c : s.toCharArray()) {  
            // 如果遇到左括号 '['  
            if(c == '[') {  
                // 将当前的重复次数入栈  
                stack_multi.addLast(multi);  
                  
                // 将当前的解码结果入栈  
                stack_res.addLast(res.toString());  
                  
                // 重置重复次数和解码结果  
                multi = 0;  
                res = new StringBuilder();  
            }  
            // 如果遇到右括号 ']'  
            else if(c == ']') {  
                // 创建一个临时StringBuilder来构建当前括号内的重复字符串  
                StringBuilder tmp = new StringBuilder();  
                  
                // 取出栈顶的重复次数  
                int cur_multi = stack_multi.removeLast();  
                  
                // 根据重复次数构建字符串  
                for(int i = 0; i < cur_multi; i++) tmp.append(res);  
                  
                // 取出栈顶的解码结果，并添加当前括号内的重复字符串  
                res = new StringBuilder(stack_res.removeLast() + tmp);  
            }  
            // 如果遇到数字  
            else if(c >= '0' && c <= '9') {  
                // 累积重复次数  
                multi = multi * 10 + Integer.parseInt(c + "");  
            }  
            // 如果遇到字母  
            else {  
                // 将字母添加到当前的解码结果中  
                res.append(c);  
            }  
        }  
          
        // 返回最终的解码字符串  
        return res.toString();  
    }  
}