📃 题目描述

题目链接：

• 394. 字符串解码 (opens new window)

🔔 解题思路

和后缀表达式 剑指 Offer II 036. 后缀表达式 - 力扣（LeetCode） (leetcode-cn.com) (opens new window) 差不多，都是将运算后的结果再入栈

这里有个小坑就是数字可能并不是只有一位，而是多位的，比如 12[ab] 这样

class Solution {

    // 字符串下标
    private int i = 0;

    public String decodeString(String s) {
        Stack<Character> stack = new Stack<>();

        while(i < s.length()) {
            char c = s.charAt(i);
            // 数字，入栈
            if (Character.isDigit(c)) {
                // 数字可能不只一位，是多位
                int num = getNum(s);
                stack.push((char)num);
            }
            // '[' or 字母，入栈
            else if (c == '[' || Character.isLowerCase(c) || Character.isUpperCase(c)) {
                // 更新待处理的下标
                i ++;

                stack.push(c);
            }
            // '['，出栈
            else if (c == ']') {
                // 更新待处理的下标
                i ++;

                // 获取 '[' 和 ']' 之间的字符串 temp
                StringBuilder temp = new StringBuilder();
                while (stack.peek() != '[') {
                    temp.append(stack.pop());
                }
                // reverse temp
                temp = temp.reverse();
                
                // '[' 出栈
                stack.pop();
                // 此时栈顶为 temp 应该出现的次数
                int repetions = stack.pop();
                // 我们根据这个次数和 temp 构造出新的字符串
                StringBuilder newTemp = new StringBuilder();
                for (int i = 0; i < repetions; i ++) {
                    newTemp.append(temp);
                }
                // 新字符串 newTemp 再进栈
                for (Character ch : newTemp.toString().toCharArray()) {
                    stack.push(ch);
                }
            }
        }

        // 栈底 -> 栈顶即为最终结果
        return getStack(stack);
    }


    // 找到从下标 i 开始的连续数字
    private int getNum(String s) {
        StringBuilder res = new StringBuilder();
        for (; i < s.length(); i ++) {
            if (!Character.isDigit(s.charAt(i))) {
                break;
            }

            res.append(s.charAt(i));
        }

        return Integer.parseInt(res.toString());
    }

    // 按照栈底 -> 栈顶的顺序输出
    private String getStack(Stack<Character> stack) {
        StringBuilder res = new StringBuilder();

        while (!stack.isEmpty()) {
            res.append(stack.pop());
        }

        return res.reverse().toString();
    }

}

💥 复杂度分析

• 空间复杂度：O(N)
• 时间复杂度：O(N)