Description
Given an encoded string, return its 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].
Example
1 | s = "3[a]2[bc]", return "aaabcbc". |
Solution
Solution 1: Stack1
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
36class Solution {
// Used Stack.
public String decodeString(String s) {
if (s == null || s.length() == 0) return s;
String res = "";
Stack<Integer> count = new Stack<>();
Stack<String> resSt = new Stack<>();
int idx = 0;
while(idx < s.length()){
if (Character.isDigit(s.charAt(idx))){
int c = 0;
while(Character.isDigit(s.charAt(idx))){
c = c * 10 + s.charAt(idx) - 48;
idx++;
}
count.push(c);
}
else if (s.charAt(idx) == '['){
resSt.push(res);
res = "";
idx++;
}
else if (s.charAt(idx) == ']'){
StringBuilder temp = new StringBuilder(resSt.pop());
int times = count.pop();
for (int i = 0; i < times; i++)
temp.append(res);
res = temp.toString();
idx++;
}
else res += s.charAt(idx++);
}
return res;
}
}
Solution 2: Recursion with queue1
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
33class Solution {
// Used recursion with Queue
public String decodeString(String s) {
if (s == null || s.length() == 0) return s;
Queue<Character> q = new LinkedList<>();
for (char ch: s.toCharArray()){
q.offer(ch);
}
return helper(q);
}
private String helper(Queue<Character> queue){
StringBuilder res = new StringBuilder();
int num = 0;
while (!queue.isEmpty()){
char ch = queue.poll();
if (Character.isDigit(ch)){
num = num * 10 + ch - 48;
}
else if (ch == '['){
String temp = helper(queue);
for (int i = 0; i < num; i++)
res.append(temp);
num = 0;
}
else if (ch == ']')
break;
else
res.append(ch);
}
return res.toString();
}
}