-
Notifications
You must be signed in to change notification settings - Fork 0
/
Decode String
114 lines (102 loc) · 3.09 KB
/
Decode String
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/*
LeetCode 394:
Given an encoded string, return it's decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].
Examples:
s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
Solution:
Language: C++
Tag: stack DFS
*/
class Solution {
public:
string decodeString(string s) {
/*
// 1. stack
stack<int> num;
stack<char> str;
int idx = 0, count = 0;
while (idx < s.length()) {
if (isCharacter(s[idx])) {
str.push(s[idx]);
} else if (isDigit(s[idx])) {
count = count * 10 + (s[idx] - '0');
} else if (s[idx] == '[') {
str.push(s[idx]);
if (count == 0) {
count = 1;
}
num.push(count);
count = 0;
} else { // ']'
string cur = getStr(str);
int cur_num = num.top();
num.pop();
while (cur_num > 0) {
for (int i = 0; i < cur.length(); ++i) {
str.push(cur[i]);
}
--cur_num;
}
}
++idx;
}
return getStr(str);
*/
// 2. DFS
int idx = 0;
return helper(s, idx);
}
string helper(string &s, int &idx) {
string res = "";
int count = 0;
while (idx < s.length() && s[idx] != ']') {
if (isCharacter(s[idx])) {
res += s[idx];
} else if (isDigit(s[idx])) {
count = count * 10 + (s[idx] - '0');
} else if (s[idx] == '[') {
count = ((count == 0) ? 1 : count);
string sub = helper(s, ++idx);
while (count > 0) {
res += sub;
--count;
}
}
++idx;
}
return res;
}
string getStr(stack<char> &str) {
stack<char> reve;
while (!str.empty() && str.top() != '[') {
reve.push(str.top());
str.pop();
}
if (!str.empty()) {
str.pop();
}
string res = "";
while(!reve.empty()) {
res += reve.top();
reve.pop();
}
return res;
}
bool isDigit(char c) {
if (c >= '0' && c <= '9') {
return true;
}
return false;
}
bool isCharacter(char c) {
if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
return true;
}
return false;
}
};