An algorithm to decode a string which is encoded in a pattern where a substring is wrapped in square brackets lead by a number.
Example
Input: "2[a2[b]]" "3[b2[ca]]" output: "abbabb" "bcacabcacabcaca"
Using two stacks to decode a string.
Implementation
- We will use two different stacks, one to store the count i.e numbers
numStack
and second to the store the sub stringcharStack
. - We will iterate the whole string on each character and check
- If the current char is number then push it to the
numStack
. - Else if the character is opening square bracket
'['
then check if there is a count number assigned to it or not. If it is then it may have already been pushed in the first condition so just add the character tocharStack
else add the current character tocharStack
and1
to thenumStack
. - If the character is closing square bracket
']'
then get the count fromnumStack
and sub string fromcharStack
and decode them, then again add the decoded string back to thecharStack
so that in the next iteration decoded sub string will be repeated along with the parent sub string. - Else the character is alphabet so add it to the
charStack
. - In the end create a string from the
charStack
(which will have decoded substring) and return it.
let decodeString = (str) => { let numStack = new Stack(); let charStack = new Stack(); let decoded = "", temp =""; for(let i = 0; i < str.length; i++){ let count = 0; let val = str[i]; //If char is number then //push to numStack if(/^\d+$/.test(val)){ numStack.push(val); }else if(val === '['){ //Else if open bracket and previous character is number //Then it will already added to numStack in the above (if condition) //Just add the char to charStack if(/^\d+$/.test(str[i-1])){ charStack.push(str[i]); }else{ //Else add 1 to numstack //And char to charStack charStack.push(str[i]); numStack.push(1); } }else if(val === ']'){ //If close bracket //Reset temp and count temp = ""; count = 0; //Get the count from numStack count = !numStack.isEmpty() && numStack.pop(); //Get the subStr from charStack while(!charStack.isEmpty() && charStack.peek() !== '['){ temp = charStack.pop() + temp; } //Remove the '[' char from charStack if(!charStack.isEmpty() && charStack.peek() === '['){ charStack.pop(); } //Create the repeat subStr decoded = temp.repeat(count); //Push the newlyCreated subStr to charStack again for(let j = 0; j < decoded.length; j++){ charStack.push(decoded[j]); } //reset the string decoded = ""; } else{ //If alpha character then add to charStack charStack.push(val); } } //Form the decoded string from charStack while(!charStack.isEmpty()){ decoded = charStack.pop() + decoded; } //Return the decoded str return decoded; }
Input: console.log(decodeString("2[a2[b]]")); console.log(decodeString("3[b2[ca]]")); Output: "abbabb" "bcacabcacabcaca"
Time complexity: O(n ^ 2).
Space complexity: O(n + n).