GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — leetcode/algorithms/cpp/decodeString/DecodeString.cpp at master · haoel/leetcode

Expand file tree

/

DecodeString.cpp

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
105 lines (92 loc) · 2.95 KB
/

DecodeString.cpp

Copy path

File metadata and controls

105 lines (92 loc) · 2.95 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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');
}
};
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.