394. 字符串解码
一句话套路双栈处理嵌套:数字栈 + 字符串栈
题目描述
给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。
测试用例保证输出的长度不会超过 105。
示例 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"
提示:
1 <= s.length <= 30s由小写英文字母、数字和方括号'[]'组成s保证是一个 有效 的输入。s中所有整数的取值范围为[1, 300]
思路
时间
O(输出长度)空间
O(嵌套层数 + 输出长度)(栈里存的串本身也是 O(输出))思路
嵌套结构 -> 双栈。一个存重复次数,一个存「进入本层之前已拼好的串」。
遇 '[' 把当前 num 和当前 cur 同时压栈并清零(开新层);
遇 ']' 弹栈:cur = 上层前缀 + 本层内容 × 次数。
数字可能多位("12[a]"),所以要 num = num*10 + (c-'0') 累积。
另解
递归下降(遇 '[' 就递归)代码更短,栈空间隐式。
图解
字符串
abcabccdcdcdef(来自本仓库测试数据,下标从 0 开始)逐帧动画
1 / 4
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0394 {
class Solution {
public:
string decodeString(const string& s) {
stack<int> nums;
stack<string> parts;
string cur;
int num = 0;
for (char c : s) {
if (isdigit((unsigned char)c)) {
num = num * 10 + (c - '0');
} else if (c == '[') {
nums.push(num); // 本层要重复几次
parts.push(cur); // 保存本层之前的内容
num = 0;
cur.clear(); // 开始收集本层内容
} else if (c == ']') {
string body = cur;
int times = nums.top();
nums.pop();
cur = parts.top(); // 回到上一层
parts.pop();
for (int i = 0; i < times; ++i) cur += body;
} else {
cur += c;
}
}
return cur;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0394::Solution s;
CHECK_EQ(s.decodeString("3[a]2[bc]"), string("aaabcbc"));
CHECK_EQ(s.decodeString("3[a2[c]]"), string("accaccacc")); // 嵌套
CHECK_EQ(s.decodeString("2[abc]3[cd]ef"), string("abcabccdcdcdef"));
CHECK_EQ(s.decodeString("abc3[cd]xyz"), string("abccdcdcdxyz"));
CHECK_EQ(s.decodeString("10[a]"), string("aaaaaaaaaa")); // 多位数字