LeetCode394 字符串解码

题目

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: 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"

方法

栈方法

使用辅助栈，遍历字符串
若当前字符为数字，则记录后面紧跟的所有数字拼成字符串存入栈
若当前字符为字母或[，则直接入栈
若当前字符为]，则出栈直到第一个[，将出栈的字符存入另一个栈中，并去除[，取出数字拼成解码的字符串存入栈中
（这里使用另一个栈而不使用StringBuffer是因为出栈的不一定是单个字符，有可能是已解码的字符串，此时用StringBuffer并反转顺序就不对了）

• 时间复杂度：O（）
• 空间复杂度：O（）

class Solution {
    private int ptr;
    public String decodeString(String s) {
        LinkedList stack  = new LinkedList<>();
        ptr = 0;
        while(ptr str = new LinkedList<>();
                while(!stack.peekLast().equals("[")){
                    str.addLast(stack.removeLast());
                }
                stack.removeLast();
                Collections.reverse(str);
                String val = getString(str);
                StringBuffer vals = new StringBuffer();
                int num = Integer.parseInt(stack.removeLast());
                for(int i=0;i stack){
        StringBuffer ans = new StringBuffer();
        for(String s:stack){
            ans.append(s);
        }
        return ans.toString();
    }
}