题目描述
小赵和小钱在练字,小钱对小赵说:你知道吗,我练习的字是有蕴含的。
小赵不服气了,凭什么你的就有蕴含呢?
小钱说,你所看到的并不是我真正练习的字,你需要将我现在写下的字符串里面 “%” 和 “#” 之间的字重复符号前的那么多倍,才能看到我真正写的是什么。
你能帮帮小赵吗?
说明:可能存在嵌套的情况,如 “3% g2% n##”,返回 “gnngnngnn”,输入输出的字符串长度都不超过 10000。
输入字符串保证合法,且输出的字符串中只包含大小写英文字母。
输入格式
一行带数字和嵌套括号的字符串。
输出格式
展开的字符串。
样例
输入样例:
3%acm#2%acm#
输出样例:
acmacmacmacmacm
算法1
(递归) 复杂度应该是 $O(n)$ 吧
开始想到用栈,但是没写出来,有些细节不知道怎么处理,看了别人的代码也没懂,就写了个这个
时间复杂度分析:顺序遍历s
C++ 代码
#include <iostream>
using namespace std;
pair<int, string> process(string s) {
string rt;
int num = 0;
for(int i = 0; i < s.length(); i++) {
if(s[i] == '%') {
auto pr = process(s.substr(i+1, s.length() - i - 1));
for(int j = 0; j < num ;j ++)
rt += pr.second;
i += pr.first + 1;
num = 0;
}
else if(s[i] == '#') return {i, rt};
else if(s[i] >= '0' && s[i] <= '9') num = num* 10 + (s[i] - '0');
else rt = rt + s[i];
}
return {1, rt};
}
int main() {
std::ios::sync_with_stdio(false);
string s;
cin>>s;
cout<<process(s).second<<endl;
return 0;
}