Decode a string recursively encoded as count followed by substring | Set 2 (using Recursion)
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 strings stack<string> ans; string res = "" ; // Recursive function to decode // the encoded string void 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 function string decodeString(string s) { decode(s, 0); return res; } // Driver code int main() { string str = "2[a2[b]]" ; cout << decodeString(str) << endl; return 0; } |
Java
// Java code to implement above approach import 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 strings ans = [] res = "" # Recursive function to decode # the encoded string def 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 function def decodeString(s): decode(s, 0 ) return res # Driver code str = "2[a2[b]]" print (decodeString( str )) # This code is contributed by shinjanpatra |
C#
// C# code to implement above approach using 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 strings let ans = []; let res = "" ; //Recursive function to decode // the encoded string function 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 function function decodeString(s) { decode(s, 0); return res; } // Driver code let str = "2[a2[b]]" ; document.write(decodeString(str) + '<br>' ); // This code is contributed by Potta Lokesh </script> |
abbabb
Time Complexity: O(N) where N is the length of the decoded string
Auxiliary Space: O(N)