-
Notifications
You must be signed in to change notification settings - Fork 2
/
DecodeString.java
95 lines (84 loc) · 2.71 KB
/
DecodeString.java
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
package Leetcode;
import java.util.ArrayDeque;
import java.util.Deque;
/**
* @author kalpak
*
* 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:
* Input: s = "3[a]2[bc]"
* Output: "aaabcbc"
*
* Example 2:
* Input: s = "3[a2[c]]"
* Output: "accaccacc"
*
* Example 3:
* Input: s = "2[abc]3[cd]ef"
* Output: "abcabccdcdcdef"
*
* Example 4:
* Input: s = "abc3[cd]xyz"
* Output: "abccdcdcdxyz"
*
* Constraints:
*
* 1 <= s.length <= 30
* s consists of lowercase English letters, digits, and square brackets '[]'.
* s is guaranteed to be a valid input.
* All the integers in s are in the range [1, 300].
*/
public class DecodeString {
public static String decodeString(String s) {
if(s.length() == 0)
return "";
String result = "";
Deque<String> stack = new ArrayDeque<>();
int num = 0;
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if(Character.isDigit(c))
num = num*10 + (int)(c - '0');
else if (c == '[') {
stack.push(num + "");
stack.push("[");
num = 0;
} else if (c == ']') {
String temp = "";
while(stack.peek() != "[")
temp = stack.pop() + temp;
stack.pop(); // pop the '[' which was used as a marker
int repeat = Integer.valueOf(stack.pop());
StringBuilder sb = new StringBuilder();
// decode temp
for(int j = 0; j < repeat; j++) {
sb.append(temp);
}
stack.push(sb.toString());
} else {
stack.push(c+"");
}
}
while(!stack.isEmpty())
result = stack.pop() + result;
return result;
}
public static void main(String[] args) {
String str1 = "3[a]2[bc]";
String str2 = "3[a2[c]]";
String str3 = "2[abc]3[cd]ef";
String str4 = "abc3[cd]xyz";
System.out.println(decodeString(str1));
System.out.println(decodeString(str2));
System.out.println(decodeString(str3));
System.out.println(decodeString(str4));
}
}