leetcode 394 字符串解码

这题利用了双栈！！！一个放重复次数，一个放重复的字母！！！很牛逼，整了接近两天！看 B 站上 java 的解法终于弄明白了！！！

下面是 python 版的代码：

class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        numStack = []
        strStack = []
        tail = ""
        num = 0
        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)
            elif c == "[":
                numStack.append(num)
                strStack.append(tail)
                tail = ""
                num = 0
            elif c == "]":
                tmp = strStack.pop()
                repeatTimes = numStack.pop()
                tmp += tail * repeatTimes
                tail = tmp
            else:
                tail += c
        return tail

原版的 Java 解法：

class Solution {
    public String decodeString(String s) {
        Deque<Integer> numStack = new ArrayDeque<>();
        Deque<String> strStack = new ArrayDeque<>();

        StringBuilder tail = new StringBuilder();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int num = c - '0';
                while (i+1 < n && Character.isDigit(i+1)) {
                    num = num * 10 + s.charAt(i + 1) - '0';
                    i++;
                }
                numStack.push(num);
            } else if (c == '[') {
                strStack.push(tail.toString());
                tail = new StringBuilder();
            } else if (c == ']') {
                StringBuilder tmp = new StringBuilder(strStack.pop());
                int repeatedTimes = numStack.pop();
                for (int j = 0; j < repeatedTimes; j++) {
                    tmp.append(tail);
                }
                tail = tmp;
            } else {
                tail.append(c);
            }
        }
        return tail.toString();
    }
}