-
Notifications
You must be signed in to change notification settings - Fork 1
/
15-decode-the-string.cpp
92 lines (88 loc) · 2.03 KB
/
15-decode-the-string.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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
using namespace std;
class Solution{
string decodedString(string& s, int& i)
{
string result;
while(i < s.size() && s[i] != ']')
{
if(s[i] >= '0' && s[i] <= '9')
{
int k = 0;
while(i < s.size() && (s[i] >= '0' && s[i] <= '9'))
{
k = (k * 10) + (s[i++] - '0');
}
i++;
string str = decodedString(s, i);
while(k--)
{
result += str;
}
i++;
}
else
{
result += s[i++];
}
}
return result;
}
string decodeStringUsingStack(string s)
{
stack<int> frequency;
stack<string> substr;
int num = 0;
int i = 0;
string current = "";
while(s[i] != '\0')
{
if(s[i] == '[')
{
substr.push(current);
frequency.push(num);
current = "";
num = 0;
}
else if(s[i] >= '0' && s[i] <= '9')
{
num = num * 10 + (s[i] - '0');
}
else if(s[i] == ']')
{
string temp = current;
int freq = frequency.top();
frequency.pop();
current = substr.top();
substr.pop();
while(freq--)
{
current += temp;
}
num = 0;
}
else
{
current += s[i];
}
i++;
}
return current;
}
public:
string decodedString(string s){
int i = 0;
return decodedString(s, i);
}
};
int main(){
int t;
cin>>t;
while(t--){
string s;
cin>>s;
Solution ob;
cout<<ob.decodedString(s)<<"\n";
}
return 0;
}