字符串解码

题意

解码 k[encoded_string] 格式的字符串，支持嵌套。k 为正整数，encoded_string 重复 k 次。

思路

扫描字符串，维护当前构建的字符串 cur 和当前累积的数字 num：

数字：累积到 num（处理多位次数）。
[：保存 cur 和 num 到栈，重置两者——开始处理内层编码。
]：弹出栈顶的前缀字符串和次数，cur = 前缀 + cur × 次数——内层解码完成，回到外层。
字母：直接追加到 cur。

栈保存的是"遇到 [ 时的外层状态"，] 时恢复并合并内层结果。嵌套编码的栈深度等于嵌套层数。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string decodeString(string s) {
        stack<string> st;
        stack<int> nums;
        string cur;
        int num = 0;
        for (char ch : s) {
            if (isdigit(ch))
                num = num * 10 + (ch - '0');
            else if (ch == '[') {
                st.push(cur);
                nums.push(num);
                cur = "";
                num = 0;
            } else if (ch == ']') {
                string tmp = cur;
                cur = st.top();
                st.pop();
                int n = nums.top();
                nums.pop();
                while (n--)
                    cur += tmp;
            } else
                cur += ch;
        }
        return cur;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    cout << Solution().decodeString(s) << '\n';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26#!/usr/bin/env python3
class Solution:
    def decodeString(self, s: str) -> str:
        st, num = [], 0
        cur = ""
        for ch in s:
            if ch.isdigit():
                num = num * 10 + int(ch)
            elif ch == "[":
                st += [cur, num]
                cur = ""
                num = 0
            elif ch == "]":
                p, n = st.pop(), st.pop()
                cur = n + cur * p
            else:
                cur += ch
        return cur


def main():
    print(Solution().decodeString(input().strip()))


if __name__ == "__main__":
    main()

复杂度

时间复杂度： $O(n \cdot k_{\max})$ ，解码后字符串长度可能远大于输入。
空间复杂度： $O(d)$ ，栈深度等于嵌套层数。

总结

嵌套编码的解码用栈保存外层状态：遇到 [ 保存当前字符串和次数，遇到 ] 恢复并拼接。关键理解 [ 是"进入内层"的信号，] 是"回到外层并合并结果"的信号。

目录

题意

思路

代码

复杂度

总结