Decodificar una string codificada recursivamente como cuenta seguida de substring | Conjunto 2 (usando recursividad)

Posted on by Rudeus Greyrat

Se proporciona una string codificada str . El patrón en el que se codifica la string es el siguiente.

<count>[sub_str] ==> La substring ‘sub_str’ aparece contando veces.

La tarea es decodificar esta string str .

Ejemplos:

Entrada: str = “1[b]”
Salida: b
Explicación: La substring ‘b’ se repite 1 vez.

Entrada: str = “2[ab]”
Salida: abab
Explicación: La substring “ab” se repite dos veces.

Entrada: str = “2[a2[b]]”
Salida: abbabb
Explicación: La substring ‘b’ se repite 2 veces y se suma a ‘a’ que forma una substring “abb”. 
Ahora esta substring se repite dos veces. Así que la string final es «abbabb».

 

Enfoque iterativo: El enfoque iterativo se menciona en el Conjunto-1 de este problema. 

Enfoque recursivo: en este artículo, el problema se resolverá utilizando Recursion y Stack . Siga el enfoque mencionado a continuación para resolver el problema.

  • Declarar una pila
  • Atraviesa recursivamente cada carácter de la string dada uno por uno. Puede haber 4 casos:
    • Caso 1: el carácter actual es ‘[‘
      • No es necesario hacer nada en este caso. Simplemente continúe con el siguiente carácter
    • Caso 2: el carácter actual es ‘]’
      • Extraiga la string temporal superior y el entero superior x de la pila
      • Repita la string temporal, x veces
      • Si el siguiente elemento superior de la pila es una string, agregue esta string repetida a la string superior
      • de lo contrario, empuje la string repetida en la pila
    • Caso 3: el carácter actual es un dígito
      • Si el carácter anterior de la string original también era un dígito, agregue este dígito al número en la parte superior de la pila
      • Si el carácter anterior era otra cosa, inserte este dígito en la pila
    • Caso 4: El carácter actual es un alfabeto
      • Si el carácter anterior de la string original también era un alfabeto, agregue este alfabeto a la string en la parte superior de la pila
      • Si el carácter anterior era otra cosa, inserte este alfabeto en la pila
  • Al final, devuelva la string en la pila e imprímala

A continuación se muestra la implementación del enfoque anterior.

C++

// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
 
// Stack to store intermediate strings
stack<string> ans;
string res = "";
 
// Recusrsive 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 = "";
 
  // Recusrsive 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 = ""
 
# Recusrsive 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

Javascript

<script>
 
// JavaScript code to implement above approach
 
// Stack to store intermediate strings
let ans = [];
let res = "";
 
// Recusrsive 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>
Producción

abbabb

Complejidad de tiempo: O(N) donde N es la longitud de la string decodificada
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por Code_r y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *