Problem
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"
Solution
This is a recursive solution I brought up in 40 minutes. I believe there are better solutions.
import java.util.*;
class Solution {
public static void main(String[] args) {
String reg = "abc3[cd]xyz";
Solution sol = new Solution();
System.out.println(sol.solve(reg));
}
private String solve(String reg) {
StringBuffer result = new StringBuffer();
char[] arr = reg.toCharArray();
for(int i = 0; i < arr.length; i++) {
char c = arr[i];
if(c - '0' >= 0 && '9' - c >= 0) {
int multi = Integer.parseInt(c + "");
int len = counter(reg.substring(i+1));
String decoded = decoder(reg.substring(i+1, i + 1 + len));
StringBuffer sb = new StringBuffer();
for(int j = 0; j < multi; j++) {
sb.append(decoded);
}
result.append(sb.toString());
i += len;
} else if(c == '[' || c == ']') {
//should never enter here
} else {
result.append(c+"");
}
}
return result.toString();
}
private String decoder(String str) {
return solve(str.substring(1, str.length()));
}
private int counter(String str) {
char[] arr = str.toCharArray();
int brackets = 0;
int i = 0;
for(i = 0; i < arr.length; i++) {
char c = arr[i];
if(c == '[')
brackets++;
if(c == ']')
brackets--;
if(brackets == 0)
break;
}
return i + 1;
}
}
The time complexity and space complexity is hard to estimate. It depends on the decoder string. It is O(length of alphabets in the decoder String + sum of numbers in the decoder String).
The space complexity also depends on the decoder string, in worst case, we have something like the following 1[2[3[4[a]]]], the depth of the caller stack is largest, and we need the most space.
