[LC]394. 字符串解码

🚩传送门：力扣题目

题目

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

编码规则为: ，表示其中方括号内部的 正好重复 次。注意 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 ，例如不会出现像 或 的输入。

示例 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. 当遇到右括号时，将栈中字符出栈，直至左括号，得到 字母集 （注意顺序问题）

   ab 入栈，出栈后会变成 ba，因此在 StringBuilder 中使用 nonamefrom.insert(0, stack.pop());

2. 再遍历左括号栈中的数字

3. 得到 数字×字母集 ，如果 栈空 直接入结果集 ，如果 栈非空，将入栈
4. 直至遍历结束栈空

官方代码

import java.util.LinkedList;
class Solution {
    public static String decodeString(String s) {
        char[] str = s.toCharArray();
        LinkedList<String> stack = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length; i++) {
            // 栈空,字符入结果集
            if (stack.isEmpty() && 'a' <= str[i] && str[i] <= 'z') {
                sb.append(str[i]);
                continue;
            }
            // 栈非空时, 除非是 ] ,否则全入栈
            if (!stack.isEmpty() && str[i] == ']') {
                StringBuilder nonamefrom = new StringBuilder();
                // 将[ 括号前的字符全部取出
                while (!stack.isEmpty() && !stack.peek().equals("[")) {
                    nonamefrom.insert(0, stack.pop());
                }
                // 吐出 [
                if (!stack.isEmpty()) stack.pop();   
                StringBuilder num = new StringBuilder();
                // 查看 [ 前面是否有数字
                while (!stack.isEmpty() && stack.peek().length() == 1 
                        && '0' <= stack.peek().charAt(0) && stack.peek().charAt(0) <= '9') {
                    num.append(stack.pop());
                }
                int intnum = 0;
                if (num.length() != 0)
                    intnum = Integer.valueOf(num.reverse().toString());
                // 获取 数字×[字符]
                StringBuilder nonameTo = new StringBuilder();
                for (int j = 0; j < intnum; j++) {
                    nonameTo.append(nonamefrom.toString());
                }
                // 保存进结果集或者入栈
                if (stack.isEmpty()) {
                    sb.append(nonameTo.toString());
                } else {
                    stack.push(nonameTo.toString());
                }
            } else {
                stack.push(str[i] + "");
            }
        }
        return sb.toString();
    }
}