做出来简单,循环或递归反复替换就行。但是如何做到高效?
- 反复替换会多次拼接字符串,效率大打折扣。
- 重复搜索 [、] 等字符也会使效率大打折扣(想一想最坏情况复杂度是多少)。
下面介绍一种高效算法。我们为每层括号保存
- head: 这层括号的首字符在 output 中的起始位置;
- repeat: 重复次数。
有多层括号,用栈 s 保存。
- 遇到“|”:可以确定这两个信息,入栈;
- 遇到“]”:出栈,从 head 到当前位置复制 repeat - 1 次;
- 遇到字母:放进 output,等出栈时复制。
整体上只扫描了一次输入串;输出串也是一直往后拼接的,没有回退。总时间复杂度和空间复杂度都是 O(输入串长度 + 输出串长度),与压缩递归层数无关。
#include <iostream> #include <tuple> #include <stack> using namespace std; int main() { string input, output; cin >> input; stack<tuple<size_t, size_t> > s; // tuple<head pos, repeat number> size_t repeat = 0; for (char c : input) { if (isalpha(c)) output.push_back(c); else if (isdigit(c)) repeat = repeat * 10 + c - '0'; else if (c == '[') repeat = 0; else if (c == '|') s.emplace(output.size(), repeat); else if (c == ']') { size_t head, tail = output.size(); tie(head, repeat) = s.top(); s.pop(); for (size_t j = 1; j < repeat; j++) output.insert(output.end(), output.begin() + head, output.begin() + tail); } } cout << output << endl; }