394. 字符串解码 Medium

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

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

解题思路

输入：一个经过编码的字符串 s

输出：返回解码后的字符串

本题属于 表达式解析栈 问题。

我们观察到只要出现了 ] 就一定会有 数字 + [字母 的形式出现

所以我们可以利用栈来存储之前出现过的字符

当遇到 ] 时我们就倒推回去寻找括号里的字母以及括号前的数字

整理好之后我们可以得到解密后的部分字符串再保存到栈中

最后我们将栈内的值都拼接起来就是解密后的字符串

代码实现

python

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []

        for char in s:
            if char != ']':
                # 如果不是右括号，直接压栈（包括字母、数字、左括号）
                stack.append(char)
            else:
                # 遇到右括号，开始解码逻辑

                # 1. 取出方括号中的字符串
                decoded_str = ''
                while stack and stack[-1] != '[':
                    decoded_str = stack.pop() + decoded_str  # 逆序拼接
                stack.pop()  # 弹出 '['

                # 2. 取出字符串前的数字（可能是多位数）
                k = ''
                while stack and stack[-1].isdigit():
                    k = stack.pop() + k  # 注意顺序

                # 3. 将重复展开后的字符串重新压入栈
                stack.append(int(k) * decoded_str)

        # 最后将栈中所有片段拼接成完整字符串返回
        return ''.join(stack)

javascript

/**
 * @param {string} s
 * @return {string}
 */
const decodeString = function(s) {
    const stack = [];

    for (c of s) {
        if (c !== ']') {
            stack.push(c);
        } else {
            let curr_str = '';
            while (stack.length && stack.at(-1) !== '[') {
                curr_str = stack.pop() + curr_str;
            }
            stack.pop();

            let curr_num = '';
            while (stack.length && /[0-9]/.test(stack.at(-1))) {
                curr_num = stack.pop() + curr_num;
            }

            stack.push(curr_str.repeat(parseInt(curr_num)));
        }
    }

    return stack.join('');
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

链接

394 国际版

394 中文版