394. Decode String

  • 40.8%

https://leetcode.com/problems/decode-string/description/

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].

1
2
3
4
5
Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

方法一:

我的代码实现:

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
class Solution {
public:
string decodeString(string s) {
int i = 0;
return helper(s, i);
}

string helper(string& s, int& i){
string res;
while(i<s.size() && s[i]!=']'){
if(!isdigit(s[i]))
res += s[i++];
else{
int n = 0;
while(i<s.size() && isdigit(s[i]))
n = n*10 + s[i++] - '0';
i++; // skip '['
string t = helper(s, i);
i++; // skip ']'
while(n-->0)
res += t;
}
}
return res;
}
};

0ms, September 13, 2016

https://discuss.leetcode.com/topic/57228/0ms-simple-c-solution

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
class Solution {
public:
string decodeString(string s, int& i) {
string res;
while(i<s.length() && s[i] != ']'){
if(!isdigit(s[i])) res += s[i++];
else{
int n = 0;
while(i < s.length() && isdigit(s[i]))
n = n* 10 + s[i++] - '0';
i++; // [
string t = decodeString(s, i);
i++; // ]
while(n-->0)
res += t;
}
}
return res;
}

string decodeString(string s){
int i = 0;
return decodeString(s, i);
}
};

https://discuss.leetcode.com/topic/57899/clean-c-recursive-solution-with-explanation

Clean C++ Recursive Solution with Explanation

Every time we meet a ‘[‘, we treat it as a subproblem so call our recursive function to get the content in that ‘[‘ and ‘]’. After that, repeat that content for ‘num’ times.
Every time we meet a ‘]’, we know a subproblem finished and just return the ‘word’ we got in this subproblem.
Please notice that the ‘pos’ is passed by reference, use it to record the position of the original string we are looking at.

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
class Solution {
public:
string decodeString(string s) {
int pos = 0;
return helper(pos, s);
}

string helper(int& pos, string s) {
int num=0;
string word = "";
for(;pos<s.size(); pos++) {
char cur = s[pos];
if(cur == '[') {
string curStr = helper(++pos, s);
for(;num>0;num--) word += curStr;
} else if (cur >= '0' && cur <='9') {
num = num*10 + cur - '0';
} else if (cur == ']') {
return word;
} else { // Normal characters
word += cur;
}
}
return word;
}
};

方法二:

主要学习栈的作用,体会其中的奥妙

我的代码实现:

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
class Solution {
public:
string decodeString(string s) {
string res;
int num = 0, n = s.size();
stack<string> st1;
stack<int> st2;
for(int i=0; i<n; i++){
if(isdigit(s[i])){
num = num*10 + s[i] - '0';
}else if(isalpha(s[i])){
res += s[i];
}else if(s[i]=='['){
st1.push(res);
st2.push(num);
res.clear();
num = 0;
}else{
string t=res;
for(int j=0; j<st2.top()-1; j++)
res += t;
res = st1.top() + res;
st2.pop();
st1.pop();
}
}
return res;
}
};

https://discuss.leetcode.com/topic/63910/c-simple-and-clear-solution

C++ simple and clear solution

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
class Solution {
public:
string decodeString(string s) {
stack<string> chars;
stack<int> nums;
string res;
int num = 0;
for(char c : s) {
if(isdigit(c)) {
num = num*10 + (c-'0');
}
else if(isalpha(c)) {
res.push_back(c);
}
else if(c == '[') {
chars.push(res);
nums.push(num);
res = "";
num = 0;
}
else if(c == ']') {
string tmp = res;
for(int i = 0; i < nums.top()-1; ++i) {
res += tmp;
}
res = chars.top() + res;
chars.pop(); nums.pop();
}
}
return res;
}
};

python

32ms, September 13, 2016

https://discuss.leetcode.com/topic/57121/share-my-python-stack-simple-solution-easy-to-understand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def decodeString(self, s):
"""
:type s: str
:rtype: str
"""
stack = []
stack.append(['', 1])
num = ''
for ch in s:
if ch.isdigit():
num += ch
elif ch == '[':
stack.append(['', int(num)])
num = ''
elif ch == ']':
st, k = stack.pop()
stack[-1][0] += st*k
else:
stack[-1][0] += ch
return stack[0][0]

java

3ms, September 13, 2016

https://discuss.leetcode.com/topic/57159/simple-java-solution-using-stack

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
public class Solution {
public String decodeString(String s) {
String res = "";
Stack<Integer> countStack = new Stack<>();
Stack<String> resStack = new Stack<>();
int idx = 0;
while(idx<s.length()){
if(Character.isDigit(s.charAt(idx))){
int count = 0;
while(Character.isDigit(s.charAt(idx))){
count = 10 * count + (s.charAt(idx) - '0');
idx++;
}
countStack.push(count);
}
else if(s.charAt(idx) == '['){
resStack.push(res);
res = "";
idx++;
}
else if(s.charAt(idx) == ']'){
StringBuilder temp = new StringBuilder (resStack.pop());
int repeatTimes = countStack.pop();
for(int i = 0; i < repeatTimes; i++)
temp.append(res);
res = temp.toString();
idx++;
}
else
res += s.charAt(idx++);
}
return res;
}
}
谢谢你,可爱的朋友。