394 Decode String

1. Question

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 like3aor2[4].
Examples:
1
s = "3[a]2[bc]", return "aaabcbc".
2
s = "3[a2[c]]", return "accaccacc".
3
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
Copied!

2. Implementation

(1) Stack
思路:这题和Basic Calculator很像,都是在scan输入字符串的过程中,当遇到特定的符号时,将之前处理的变量进行一些操作。Basic Calculator是进行四则运算,这里则是decode。所以对于这类问题,stack非常合适。但有一些不同的是,这里不仅要处理数字,还有string,所以我们用两个stack:num和letters 分别存放数字和已经decode的string。
(1) 当遇到数字时,处理方式和Basic Calculator一样,这里我们存放在count这个变量里,当遇到字母时,放在一个StringBuilder里,这里我们将这个StringBuilder命名为 res
(2) 当遇到'['时,说明有新的一部分需要decode,将之前得到count和res, 存放在不同的两个stack,并将两个变量的值清空
(3) 当遇到']'时,说明有一部分已经decode完成,从num中pop出数字,从letters中pop出之前已经decode的string,按照数字把当前获得的string加到已经解析的string的部分
1
class Solution {
2
public String decodeString(String s) {
3
if (s == null || s.length() == 0) {
4
return "";
5
}
6
7
int count = 0;
8
Stack<Integer> num = new Stack<>();
9
Stack<StringBuilder> letters = new Stack<>();
10
StringBuilder res = new StringBuilder();
11
StringBuilder curStr = null;
12
13
for (char c : s.toCharArray()) {
14
if (Character.isDigit(c)) {
15
count = 10 * count + c - '0';
16
}
17
else if (c == '[') {
18
num.push(count);
19
letters.push(res);
20
count = 0;
21
res = new StringBuilder();
22
}
23
else if (c == ']') {
24
curStr = res;
25
res = letters.pop();
26
for (int i = num.pop(); i > 0; i--) {
27
res.append(curStr);
28
}
29
}
30
else {
31
res.append(c);
32
}
33
}
34
return res.toString();
35
}
36
}
Copied!
(2) DFS
1
public class Solution {
2
public String decodeString(String s) {
3
int[] index = new int[1];
4
return dfs(s, index);
5
}
6
7
public String dfs(String s, int[] index) {
8
String res = "";
9
int len = s.length();
10
int count = 0;
11
12
while (index[0] < len) {
13
if (Character.isDigit(s.charAt(index[0]))) {
14
count = 10 * count + s.charAt(index[0]) - '0';
15
}
16
else if (s.charAt(index[0]) == '[') {
17
// Skip '['
18
++index[0];
19
String nextStr = dfs(s, index);
20
while (count > 0) {
21
res += nextStr;
22
--count;
23
}
24
}
25
else if (s.charAt(index[0]) == ']') {
26
return res;
27
}
28
else {
29
res += s.charAt(index[0]);
30
}
31
++index[0];
32
}
33
return res;
34
}
35
}
Copied!

3. Time & Space Complexity

Stack: 时间复杂度O(n), 空间复杂度O(n)
DFS: 时间复杂度O(n), 空间复杂度O(n)