An encoded string str is given. The pattern in which the string is encoded is as follows.
<count>[sub_str] ==> The substring ‘sub_str’ appears count times.
The task is to decode this string str.
Examples:
Input: str = “1[b]”
Output: b
Explanation: The substring ‘b’ is repeated 1 time.Input: str = “2[ab]”
Output: abab
Explanation: The substring “ab” is repeated two times.Input: str = “2[a2[b]]”
Output: abbabb
Explanation: The substring ‘b’ is repeated 2 times and added to ‘a’ which forms a substring “abb”.
Now this substring is repeated two time. So the final string is “abbabb”.
Iterative Approach: The iterative approach is mentioned in the Set-1 of this problem.
Recursive Approach: In this article, the problem will be solved using Recursion and Stack. Follow the approach mentioned below to solve the problem
- Declare a stack
- Recursively traverse each character of the given string one by one. There can be 4 cases:
- Case 1: Current character is ‘[‘
- No need to do anything in this case. Just continue to next character
- Case 2: Current character is ‘]’
- Pop the top string temp and top integer x from the stack
- Repeat the string temp, x times
- If the next top element in the stack is a string, append this repeated string to the top string
- else push the repeated string into the stack
- Case 3: Current character is a digit
- If previous char of original string was also a digit, append this digit to the number on top of the stack
- If previous char was something else, push this digit into the stack
- Case 4: Current character is an alphabet
- If previous char of original string was also an alphabet, append this alphabet to the string on top of the stack
- If previous char was something else, push this alphabet into the stack
- Case 1: Current character is ‘[‘
- At the end, return the string in the stack and print it
Below is the implementation of the above approach.
C++
// C++ code to implement above approach#include <bits/stdc++.h>using namespace std;// Stack to store intermediate stringsstack<string> ans;string res = "";// Recursive function to decode // the encoded stringvoid decode(string s, int i){ if (i == s.length()) { res = ans.top(); return; } // If the string character is '[' if (s[i] == '['); // If the string character is ']' else if (s[i] == ']') { string temp = ans.top(); ans.pop(); int x = stoi(ans.top()); ans.pop(); for (string j = temp; x > 1; x--) temp = temp + j; string temp1 = ans.empty() == false ? ans.top() : ""; if (!temp1.empty() && !(temp1[0] - '0' < 10)) { ans.pop(); temp1 = temp1 + temp; ans.push(temp1); } else { ans.push(temp); } } // If string character is a digit else if (s[i] - '0' < 10) { string temp = ans.empty() == false ? ans.top() : ""; if (!temp.empty() && temp[0] - '0' < 10 && s[i - 1] - '0' < 10) { ans.pop(); temp = temp + s[i]; ans.push(temp); } else { temp = s[i]; ans.push(temp); } } // If the string character is alphabet else if (s[i] - 'a' < 26) { string temp = ans.empty() == false ? ans.top() : ""; if (!temp.empty() && temp[0] - 'a' >= 0 && temp[0] - 'a' < 26) { ans.pop(); temp = temp + s[i]; ans.push(temp); } else { temp = s[i]; ans.push(temp); } } // Recursive call for next index decode(s, i + 1);}// Function to call the recursive functionstring decodeString(string s){ decode(s, 0); return res;}// Driver codeint main(){ string str = "2[a2[b]]"; cout << decodeString(str) << endl; return 0;} |
Java
// Java code to implement above approachimport java.util.*;class GFG{ // Stack to store intermediate Strings static Stack<String> ans = new Stack<String>(); static String res = ""; // Recursive function to decode // the encoded String static void decode(char[] s, int i) { if (i == s.length) { res = ans.peek(); return; } // If the String character is '[' if (s[i] == '['); // If the String character is ']' else if (s[i] == ']') { String temp = ans.peek(); ans.pop(); int x = Integer.valueOf(ans.peek()); ans.pop(); for (String j = temp; x > 1; x--) temp = temp + j; String temp1 = ans.isEmpty() == false ? ans.peek() : ""; if (!temp1.isEmpty() && !(temp1.charAt(0) - '0' < 10)) { ans.pop(); temp1 = temp1 + temp; ans.add(temp1); } else { ans.add(temp); } } // If String character is a digit else if (s[i] - '0' < 10) { String temp = ans.isEmpty() == false ? ans.peek() : ""; if (!temp.isEmpty() && temp.charAt(0) - '0' < 10 && s[i - 1] - '0' < 10) { ans.pop(); temp = temp + s[i]; ans.add(temp); } else { temp = String.valueOf(s[i]); ans.add(temp); } } // If the String character is alphabet else if (s[i] - 'a' < 26) { String temp = ans.isEmpty() == false ? ans.peek() : ""; if (!temp.isEmpty() && temp.charAt(0) - 'a' >= 0 && temp.charAt(0) - 'a' < 26) { ans.pop(); temp = temp + s[i]; ans.add(temp); } else { temp = String.valueOf(s[i]); ans.add(temp); } } // Recursive call for next index decode(s, i + 1); } // Function to call the recursive function static String decodeString(String s) { decode(s.toCharArray(), 0); return res; } // Driver code public static void main(String[] args) { String str = "2[a2[b]]"; System.out.print(decodeString(str) +"\n"); }}// This code is contributed by shikhasingrajput |
Python3
# Python code to implement above approach # Stack to store intermediate stringsans = []res = ""# Recursive function to decode # the encoded stringdef decode(s, i): global res global ans if (i == len(s)): res = ans[len(ans) - 1] return # If the string character is '[' if (s[i] == '['): pass # If the string character is ']' elif (s[i] == ']'): temp = ans[len(ans) - 1] ans.pop() x = int(ans[len(ans) - 1]) ans.pop() j = temp while(x>1): temp = temp + j x -= 1 temp1 = ans[len(ans) - 1] if len(ans) != 0 else "" if len(temp1) != 0 and ~(ord(temp1[0]) - ord('0') < 10): ans.pop() temp1 = temp1 + temp ans.append(temp1) else: ans.append(temp) # If string character is a digit elif(ord(s[i]) - ord('0') < 10): temp = ans[len(ans) - 1] if len(ans) != 0 else "" if(len(temp) != 0 and ord(temp[0]) - ord('0') < 10 and ord(s[i - 1]) - ord('0') < 10): ans.pop() temp = temp + s[i] ans.append(temp) else: temp = s[i] ans.append(temp) # If the string character is alphabet elif (ord(s[i]) - ord('a') < 26): temp = ans[len(ans) - 1] if (len(ans) != 0) else "" if(temp != 0 and ord(temp[0]) - ord('a') >= 0 and ord(temp[0]) - ord('a') < 26): ans.pop() temp = temp + s[i] ans.append(temp) else: temp = s[i] ans.append(temp) # Recursive call for next index decode(s, i + 1)# Function to call the recursive functiondef decodeString(s): decode(s, 0) return res# Driver codestr = "2[a2[b]]"print(decodeString(str))# This code is contributed by shinjanpatra |
C#
// C# code to implement above approachusing System;using System.Collections.Generic;class GFG{ // Stack to store intermediate Strings static Stack<String> ans = new Stack<String>(); static String res = ""; // Recursive function to decode // the encoded String static void decode(char[] s, int i) { if (i == s.Length) { res = ans.Peek(); return; } // If the String character is '[' if (s[i] == '['); // If the String character is ']' else if (s[i] == ']') { String temp = ans.Peek(); ans.Pop(); int x = int.Parse(ans.Peek()); ans.Pop(); for (String j = temp; x > 1; x--) temp = temp + j; String temp1 = ans.Count > 0 ? ans.Peek() : ""; if (temp1.Length > 0 && !(temp1[0] - '0' < 10)) { ans.Pop(); temp1 = temp1 + temp; ans.Push(temp1); } else { ans.Push(temp); } } // If String character is a digit else if (s[i] - '0' < 10) { String temp = ans.Count > 0 ? ans.Peek() : ""; if (temp.Length > 0 && temp[0] - '0' < 10 && s[i - 1] - '0' < 10) { ans.Pop(); temp = temp + s[i]; ans.Push(temp); } else { temp = char.ToString(s[i]); ans.Push(temp); } } // If the String character is alphabet else if (s[i] - 'a' < 26) { String temp = ans.Count > 0 ? ans.Peek() : ""; if (temp.Length > 0 && temp[0] - 'a' >= 0 && temp[0] - 'a' < 26) { ans.Pop(); temp = temp + s[i]; ans.Push(temp); } else { temp = char.ToString(s[i]); ans.Push(temp); } } // Recursive call for next index decode(s, i + 1); } // Function to call the recursive function static String decodeString(String s) { decode(s.ToCharArray(), 0); return res; } // Driver code public static void Main() { String str = "2[a2[b]]"; Console.WriteLine(decodeString(str)); }}// This code is contributed by Saurabh Jaiswal |
Javascript
<script>// JavaScript code to implement above approach // Stack to store intermediate stringslet ans = [];let res = "";//Recursive function to decode // the encoded stringfunction decode(s, i){ if (i == s.length) { res = ans[ans.length - 1]; return; } // If the string character is '[' if (s[i] == '['); // If the string character is ']' else if (s[i] == ']') { let temp = ans[ans.length - 1]; ans.pop(); let x = (ans[ans.length - 1]); ans.pop(); for(let j = temp; x > 1; x--) temp = temp + j; let temp1 = ans.length != 0 ? ans[ans.length - 1] : ""; if (!temp1.length == 0 && !(temp1[0].charCodeAt(0) - '0'.charCodeAt(0) < 10)) { ans.pop(); temp1 = temp1 + temp; ans.push(temp1); } else { ans.push(temp); } } // If string character is a digit else if (s[i].charCodeAt(0) - '0'.charCodeAt(0) < 10) { let temp = ans.length != 0 ? ans[ans.length - 1] : ""; if (!temp.length == 0 && temp[0].charCodeAt(0) - '0'.charCodeAt(0) < 10 && s[i - 1].charCodeAt(0) - '0'.charCodeAt(0) < 10) { ans.pop(); temp = temp + s[i]; ans.push(temp); } else { temp = s[i]; ans.push(temp); } } // If the string character is alphabet else if (s[i].charCodeAt(0) - 'a'.charCodeAt(0) < 26) { let temp = ans.length != 0 ? ans[ans.length - 1] : ""; if (!temp.length == 0 && temp[0].charCodeAt(0) - 'a'.charCodeAt(0) >= 0 && temp[0].charCodeAt(0) - 'a'.charCodeAt(0) < 26) { ans.pop(); temp = temp + s[i]; ans.push(temp); } else { temp = s[i]; ans.push(temp); } } // Recursive call for next index decode(s, i + 1);}// Function to call the recursive functionfunction decodeString(s) { decode(s, 0); return res;}// Driver codelet str = "2[a2[b]]";document.write(decodeString(str) + '<br>');// This code is contributed by Potta Lokesh</script> |
Output
abbabb
Time Complexity: O(N) where N is the length of the decoded string
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
