Suppose, you are given an encoded string. A string is encoded in some kind of pattern, your task is to decode the string.
Let us say, < no of times string occurs > [string ]
Table of Contents
Example
Input
3[b]2[bc]
Output
bbbcaca
Explanation
Here “b” occurs 3times and “ca” occur 2 times.
Input
2[b2[d]]
Output
bddbdd
Explanation
Here it will work in two parts first it will expand “d” 2 times so it will become 2[bdd] then if we repeat this twice it will be bddbdd.
Algorithm for Decode String
- Set temp and output to an empty string, we will use it later temporarily storing the strings.
- Starting from 0, while i less than string length:
check if str[i] is equal to the digit, push it to integer stack. - Else if str [i] is equal to any character except ‘] ’, push it to character stack.
- If ‘]’ is found then pop the number from integer stack and pop all the characters from character stack and store it to the temporary string until ‘[ ’is found and pop ‘[’.
- Store and add the value of temp to output until the number pop from integer stack.
- From the output string, push all the characters into a character stack and set the output to an empty string.
- Repeat this process until all the characters from the character stack and integers from the integer stack are popped().
- Pop all the characters from the character stack and store it into output.
- Return output
Explanation for Decode String
We are given a string which is decoded in some pattern, we have to encode it and return a suitable string which verifies the decoded string, for this, we are going to use two different stacks. In one we are going to store integers and in other stack, characters.
Suppose we are given a string, 3[b2[ca]], it means it should output 2 times ac that means “caca” and now it concat with b so inside it will become “bcaca” and this string it occurs 3 times, so it will become bcacabcacabcaca.
Let us take an example
Example of Decode String
Input: 3[b2[ca]]
i=0;
str[i] =3 it will push into integer stack
i=1;
str[i] = ‘[’ it will push into character stack.
i=2;
str[i] =b, it will push into character stack
i=3;
str[i] = ‘2’ it will push into integer stack.
i=4;
str[i] =‘[’ , it will push into character stack
i=5;
str[i] = ‘c’ it will push into character stack.
i=6;
str[i] = ‘a’ it will push into character stack.
i=7;
str[i] = ‘ ] ’ according to the algorithm, if we find this ‘]’, we need to pop integer from integer stack that is 2 now and we need to pop the character one by one and store it to temporary string from the character stack until we found ‘[ ’ this character and at last pop this character.
So now temp will be “ca”.
We will multiply that temp string as no of times as the number we popped from the integer stack and that is noOfInteger = 2 and store it to output.
So the output of Decode String will become “caca” after taking it in we need to push it again into character stack.
i=8;
str[i]= “] ”, again we found this, we need to pop integer from integer stack that is 3 now, and we need to pop the character one by one and store it to temporary string from the character stack until we found ‘[ ’ this character and at last pop this character.
So now temp will be “bcaca”.
We will multiply that temp string as no of times as the number we popped from the integer stack and that is noOfInteger = 3 and store it to output.
So the output will become “bcacabcacabcaca”.
And after this, the length of the string is reached we return output.
Our output will be: “bcacabcacabcaca”.
Implementation for Decode String
C++ Program
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
string getDecodeString(string str)
{
stack<int> pushInt ;
stack<char> charStack ;
string temp = "";
string output = "";
for (int i = 0; i < str.length(); i++)
{
int noOfInteger = 0;
if (isdigit(str[i]))
{
while (isdigit(str[i]))
{
noOfInteger = noOfInteger * 10 + str[i] - '0';
i++;
}
i--;
pushInt.push(noOfInteger);
}
else if (str[i] == ']')
{
temp = "";
noOfInteger = 0;
if (!pushInt.empty())
{
noOfInteger = pushInt.top();
pushInt.pop();
}
while (!charStack.empty() && charStack.top()!='[' )
{
temp = charStack.top() + temp;
charStack.pop();
}
if (!charStack.empty() && charStack.top() == '[')
{
charStack.pop();
}
for (int j = 0; j < noOfInteger; j++)
{
output = output + temp;
}
for (int j = 0; j < output.length(); j++)
{
charStack.push(output[j]);
}
output = "";
}
else if (str[i] == '[')
{
if (isdigit(str[i-1]))
{
charStack.push(str[i]);
}
else
{
charStack.push(str[i]);
pushInt.push(1);
}
}
else
{
charStack.push(str[i]);
}
}
while (!charStack.empty())
{
output = charStack.top() + output;
charStack.pop();
}
return output;
}
int main()
{
string str = "3[b2[ca]]";
cout<<getDecodeString(str);
return 0;
}
bcacabcacabcaca
Java Program
import java.util.Stack;
class stringDecoding
{
static String getDecodeString(String str)
{
Stack<Integer> pushInt = new Stack<>();
Stack<Character> charStack = new Stack<>();
String temp = "";
String output = "";
for (int i = 0; i < str.length(); i++)
{
int noOfInteger = 0;
if (Character.isDigit(str.charAt(i)))
{
while (Character.isDigit(str.charAt(i)))
{
noOfInteger = noOfInteger * 10 + str.charAt(i) - '0';
i++;
}
i--;
pushInt.push(noOfInteger);
}
else if (str.charAt(i) == ']')
{
temp = "";
noOfInteger = 0;
if (!pushInt.isEmpty())
{
noOfInteger = pushInt.peek();
pushInt.pop();
}
while (!charStack.isEmpty() && charStack.peek()!='[' )
{
temp = charStack.peek() + temp;
charStack.pop();
}
if (!charStack.empty() && charStack.peek() == '[')
{
charStack.pop();
}
for (int j = 0; j < noOfInteger; j++)
{
output = output + temp;
}
for (int j = 0; j < output.length(); j++)
{
charStack.push(output.charAt(j));
}
output = "";
}
else if (str.charAt(i) == '[')
{
if (Character.isDigit(str.charAt(i-1)))
{
charStack.push(str.charAt(i));
}
else
{
charStack.push(str.charAt(i));
pushInt.push(1);
}
}
else
{
charStack.push(str.charAt(i));
}
}
while (!charStack.isEmpty())
{
output = charStack.peek() + output;
charStack.pop();
}
return output;
}
public static void main(String args[])
{
String str = "3[b2[ca]]";
System.out.println(getDecodeString(str));
}
}
bcacabcacabcaca
Illustration of above code
Complexity Analysis
Time Complexity
Here time complexity is not fixed because it depends upon the input string because each time we repeat some step and concatenate a string
Space Complexity
O(n) where n is the length of the string. We use a stack for implement and the maximum possible size of the stack is n.