An encoded string (s) is given, the task is to decode it. The pattern in which the strings are encoded is as follows.
<count>[sub_str] ==> The substring 'sub_str' appears count times.
Input : str = "1[b]" Output : b Input : str = "2[ab]" Output : abab Input : str = "2[a2[b]]" Output : abbabb Input : str = "3[b2[ca]]" Output : bcacabcacabcaca
The idea is to use two stacks, one for integers and another for characters.
Now, traverse the string,
- Whenever we encounter any number, push it into the integer stack and in case of any alphabet (a to z) or open bracket (‘[‘), push it onto the character stack.
- Whenever any close bracket (‘]’) is encounter pop the character from the character stack until open bracket (‘[‘) is not found in the character stack. Also, pop the top element from the integer stack, say n. Now make a string repeating the popped character n number of time. Now, push all character of the string in the stack.
Below is implementation of this approach:
<!—-Illustration of above code for “3[b2[ca]]”>
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.