05 August 2008
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
2
3
4
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].
Recursion
Time Complexity: O(maxK * N), where maxK is the maximum value of K and N is the length of a given string s. We traverse a string of size N and iterate K times to decode each pattern of the form K[string]. This gives us worst case time complexity as O(maxK * N).
Space Complexity: O(N), space used to store the internal call stack used for recursion. As we are recursively decoding each nested pattern, the maximum depth of recursive call stack would not be more than N.
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
class Solution {
int index = 0;
String decodeString(String s) {
StringBuilder stringBuilder = new StringBuilder();
while (index < s.length() && s.charAt(index) != ']') {
if (!Character.isDigit(s.charAt(index))) {
stringBuilder.append(s.charAt(index++));
} else {
int K = 0;
// Build K while next character is a digit
while (index < s.length() && Character.isDigit(s.charAt(index))) {
K = K * 10 + Character.getNumericValue(s.charAt(index));
index++;
}
// Ignore the opening bracket '['
index++;
String decodedString = decodeString(s);
// Ignore the closing bracket ']'
index++;
// Build K[decodedString] and append to the stringBuilder
while (K-- > 0) {
stringBuilder.append(decodedString);
}
}
}
return stringBuilder.toString();
}
}
Iteratie, 2 stacks
Time Complexity: O(maxK * N), where maxK is the maximum value of K and N is the length of a given string s. We traverse a string of size N and iterate K times to decode each pattern of the form K[string]. This gives us worst case time complexity as O(maxK * N).
Space Complexity: O(N + M), where N is the number of letters (a-z) and M is the number of digits (0-9) in string s. In worst case, the maximum size of stringStack and countStack could be N and M respectively.
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
class Solution {
String decodeString(String s) {
Deque<Integer> countStack = new ArrayDeque<>();
Deque<StringBuilder> stringStack = new ArrayDeque<>();
StringBuilder currentString = new StringBuilder();
int K = 0;
for (char currentChar : s.toCharArray()) {
if (Character.isDigit(currentChar)) {
K = K * 10 + Character.getNumericValue(currentChar);
} else if (currentChar == '[') {
// Push the number K to countStack
countStack.push(K);
// Push the currentString to stringStack
stringStack.push(currentString);
// Reset currentString and K
currentString = new StringBuilder();
K = 0;
} else if (currentChar == ']') {
StringBuilder prevString = stringStack.pop();
// Decode currentK[currentString] by appending currentString K times to prevString
for (int currentK = countStack.pop(); currentK > 0; currentK--) {
prevString.append(currentString);
}
currentString = prevString;
} else {
currentString.append(currentChar);
}
}
return currentString.toString();
}
}