LeetCode 394. 字符串解码

思路：读完题目后，大概知道要用表达式求值的类似思路来做，从左到右遍历，并引入栈来保存中间结果。

但始终没有想明白。

需要注意的点有：

• 数字不一定是小于10的，可能是两位数甚至三位数（解析数字时不能只解析单个位置）
• 数字后一定会跟一个左括号[
• 括号可以进行嵌套，如3[a2[df5[kp]e]]，但是有一个点，括号一定是和数字一起出现的

由于我们在处理一个左括号[时，可能这个左括号还没结尾（还没有遇到右括号]），就遇到了另一个左括号[，此时需要把这个左括号前已经得到的字符串做一下暂存。

同时也要注意，出现的字母，可能是位于括号中，也可能不位于括号中，比如abc3[pk]elk,极端的情况是一个括号也没有，比如abcd

一个思路很清晰的代码如下（对单个字符进行存储，代码很好理解，但是效率不见得高）

class Solution {
    public String decodeString(String s) {
        Deque<Character> stack = new LinkedList<>();
        for (char c : s.toCharArray()) {
            if (']' != c) stack.push(c);
            else {
                StringBuilder sb = new StringBuilder();
                while (!stack.isEmpty() && stack.peek() != '[') sb.insert(0, stack.pop());
                stack.pop(); // d出 [
                StringBuilder numSb = new StringBuilder();
                while (!stack.isEmpty() && Character.isDigit(stack.peek())) numSb.insert(0, stack.pop());
                int num = Integer.parseInt(numSb.toString());
                for (int i = 1; i <= num; i++) {
                    for (char cc : sb.toString().toCharArray()) stack.push(cc);
                }
            }
        }
        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty()) res.insert(0, stack.pop());
        return res.toString();
    }
}

分开两个栈，数字栈和字符串栈，该代码不是很好理解

class Solution {
    public String decodeString(String s) {
        Deque<Integer> numStack = new LinkedList<>();
        Deque<StringBuilder> strStack = new LinkedList<>();
        StringBuilder cur = new StringBuilder();
        int num = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) num = num * 10 + c - '0';
            else if ('[' == c) {
                strStack.push(cur);
                cur = new StringBuilder(); // 这里必须要new 一个新的对象, 不能调 setLength(0) 来清空, 因为这个cur被push到栈中, 持有的是引用，会影响栈中原有的元素
                numStack.push(num);
                num = 0;
            } else if (']' == c) {
                StringBuilder sb = strStack.pop();
                int t = numStack.pop();
                for (int i = 0; i < t; i++) sb.append(cur);
                cur = sb;
            } else {
                cur.append(c);
            }
        }
        return cur.toString();
    }
}

我觉得好难啊这道题！明明思路和表达式求值（逆波兰式）类似，但为什么只想得出大概思路，但要动手写代码就是无从下手呢！！
一道题花了我一个早上，wssb。

还要继续努力啊。