跳到主要内容

LeetCode 394. 字符串解码

本节目标

用栈保存进入方括号前的外层字符串和重复次数，在右括号处恢复嵌套结果。

这道题属于解析与大整数中的嵌套解析模板：左括号保存外层状态，右括号恢复已完成的内层结果。

查看原题

题意与约束​

编码格式为 k[encoded_string]，其中 k 可以是多位数字，方括号内还可以继续嵌套编码。需要返回完整解码后的字符串。

栈保存外层状态​

顺序扫描字符并累计连续数字。遇到 [ 时，把当前的重复次数和外层字符串压栈，再开始构造新的内层字符串；遇到 ] 时，当前字符串正好是完整内层结果，弹出对应状态并将其重复后接回外层。

不变量​

任何时刻，current 都是当前最内层尚未闭合方括号内已解码的内容；栈顶保存其直接外层在进入该方括号前的状态。右括号只恢复一层，因此嵌套结构会从内向外自然展开。

代码实现​

C++17
#include <cctype>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string decodeString(string s) {
        vector<int> counts;
        vector<string> outerStrings;
        string current;
        int count = 0;

        for (char character : s) {
            if (isdigit(character)) {
                count = count * 10 + (character - '0');
            } else if (character == '[') {
                counts.push_back(count);
                outerStrings.push_back(current);
                count = 0;
                current.clear();
            } else if (character == ']') {
                string decoded;
                for (int index = 0; index < counts.back(); index++) {
                    decoded += current;
                }
                current = outerStrings.back() + decoded;
                outerStrings.pop_back();
                counts.pop_back();
            } else {
                current.push_back(character);
            }
        }

        return current;
    }
};

复杂度分析​

设编码串长度为 N、解码后的字符串长度为 L、最大嵌套深度为 D。扫描编码串需要 O(N)；当前实现会在每层右括号处复制已经完成的内层结果，因此时间复杂度为 O(N + LD)，最坏可达 O(N + L²)。栈中保存的外层片段与当前结果合计占用 O(L) 空间，输出本身也需要 O(L) 空间。

易错点​

  • 将 10[a] 的重复次数读成 1 和 0 两次独立操作。
  • 在 ] 处先清空内层字符串，再尝试重复它。
  • 只保存重复次数，不保存进入内层前已经构造好的外层字符串。

模式迁移​

对其他括号嵌套、标签嵌套或可递归序列，遇到进入内层的标记时保存外层状态，遇到结束标记时恢复完整内层结果。