forked from haoel/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDecodeString.cpp
More file actions
105 lines (92 loc) · 2.95 KB
/
Copy pathDecodeString.cpp
File metadata and controls
105 lines (92 loc) · 2.95 KB
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
// Source : https://leetcode.com/problems/decode-string/
// Author : Hao Chen
// Date : 2016-09-08
/***************************************************************************************
*
* 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".
***************************************************************************************/
class Solution {
public:
string decodeString(string s) {
if (!isValid(s)) return "";
stack<string> _stack;
stack<int> _nstack;
string result;
string tmp;
int n=0;
for (int i=0; i<s.size(); i++) {
if ( isNum(s[i]) ) {
n = 0;
for(; isNum(s[i]); i++ ) {
n = n*10 + s[i] - '0';
}
}
if (s[i] == '[') {
tmp="";
_stack.push(tmp);
_nstack.push(n);
} else if (s[i] == ']') {
n = _nstack.top();
tmp="";
for (; n>0; n--) {
tmp += _stack.top();
}
_stack.pop();
_nstack.pop();
if ( ! _stack.empty() ) {
_stack.top() += tmp;
}else {
result += tmp;
}
} else {
if ( ! _stack.empty() ) {
_stack.top() += s[i];
} else {
result += s[i];
}
}
}
return result;
}
private:
//only check the following rules:
// 1) the number must be followed by '['
// 2) the '[' and ']' must be matched.
bool isValid(string& s) {
stack<char> _stack;
for (int i=0; i<s.size(); i++) {
if ( isNum(s[i]) ) {
for(; isNum(s[i]); i++);
if (s[i] != '[') {
return false;
}
_stack.push('[');
continue;
} else if (s[i] == ']' ) {
if ( _stack.top() != '[' ) return false;
_stack.pop();
}
}
return (_stack.size() == 0);
}
bool isNum(char ch) {
return (ch>='0' && ch<='9');
}
};