习题

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

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

算法思路

本题的第一个难点在于嵌套括号，与栈的先进后出相互对应，所以我们可以使用栈来进行辅助

本题的第二个难点在于数字和字母都可能是连续的，所以我们可以使用两个栈，分别来保存数字和字母

定义当前字符串 str，当前数字num，数字栈numStack，字母栈strStack

遍历s中的每个字母，假设定义为current

1. current 为数字时，num = num * 10 + current
2. current 为字母时，str = str + current
3. current 为 [ 时，将字符串和数字推入栈中，并重置它们
4. current 为 ] 时，拼接字符串 str = last_str + mul * str，其中：
1. last_str 是上个 [ 到当前 [ 的字符串，例如 "3[a2[c]]" 中的 a
2. mul 是当前 [ 到 ] 内字符串的重复倍数，例如 "3[a2[c]]" 中的 2

复杂度分析

• 时间复杂度 O(N)，一次遍历 s
• 空间复杂度 O(N)

代码

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function(s) {
    var numStack = [],
        strStack = [],
        num = 0,
        str = "";
    for (var i = 0; i < s.length; i++) {
        var current = s[i];
        if (current == '[') {
            numStack.push(num);
            strStack.push(str);
            num = 0;
            str = "";
        } else if (current == ']') {
            str = strStack.pop() + str.repeat(numStack.pop());
        } else if (isNaN(current)) { // 字母
            str += current;
        } else {  // 数字
            num = num * 10 + Number(current);
        }
    }
    return str;
};