Decode a string recursively encoded as count followed by substring | Set 2 (using Recursion)

0 0 7 minutes read

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
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>

Output

abbabb

Time Complexity: O(N) where N is the length of the decoded string
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!