The challenge
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 <= 30sconsists of lowercase English letters, digits, and square brackets'[]'.sis guaranteed to be a valid input.- All the integers in
sare in the range[1, 300].
Let’s start by writing some Test cases
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;
class DecodeStringTest {
DecodeString ds = new DecodeString();
@Test
void decodeString1() {
String actual = ds.decodeString("3[a]2[bc]");
String expected = "aaabcbc";
assertEquals(expected, actual);
}
@Test
void decodeString2() {
String actual = ds.decodeString("3[a2[c]]");
String expected = "accaccacc";
assertEquals(expected, actual);
}
@Test
void decodeString3() {
String actual = ds.decodeString("2[abc]3[cd]ef");
String expected = "abcabccdcdcdef";
assertEquals(expected, actual);
}
@Test
void decodeString4() {
String actual = ds.decodeString("abc3[cd]xyz");
String expected = "abccdcdcdxyz";
assertEquals(expected, actual);
}
}
This is all pretty simple, nothing onerous here so far.
The solution in Java code
At first we could try and knock out something like the following:
public class DecodeString {
public String decodeString(String s) {
StringBuilder sb = new StringBuilder();
for (int i=0; i<s.length(); i++) {
if (Character.isDigit(s.charAt(i))) {
int timesToRepeat = Integer.parseInt(""+s.charAt(i));
StringBuilder repeats = new StringBuilder();
for (int j=++i; j<s.length(); j++) {
if (s.charAt(j)=='[') {
//start of group
} else if (s.charAt(j)==']') {
//end of group
break;
} else {
//has repeat character
repeats.append(s.charAt(j));
}
i++;
}
sb.append(repeats.toString().repeat(timesToRepeat));
} else {
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}
BUT! When we run this against our test cases, we’ll notice the following:
org.opentest4j.AssertionFailedError:
Expected :accaccacc
Actual :a2ca2ca2c]
This is because test-case number 2 makes our lives a little harder by requiring a wrapped expression:
So attempt number 2 at this solution would be to approach the problem from the perspective of a stack:
import java.util.Stack;
public class DecodeString {
public String decodeString(String s) {
Stack<Integer> freqStack = new Stack<>();
Stack<StringBuilder> strStack = new Stack<>();
StringBuilder currStr = new StringBuilder();
int k =0;
for(char c : s.toCharArray()){
if(Character.isDigit(c)){
k = k*10 + (c-'0');
} else if (Character.isLetter(c)){
currStr.append(c);
} else if(c == '['){
freqStack.push(k);
strStack.push(currStr);
k =0;
currStr = new StringBuilder();
} else if(c == ']'){
StringBuilder temp = currStr;
int freq = freqStack.pop();
currStr = strStack.pop();
while(freq-->0){
currStr.append(temp);
}
k = 0;
}
}
return currStr.toString();
}
}
