Descifrar el mensaje del código dado reemplazando todo * con valores de prefijo de string codificada

Dada una string str de longitud N que está codificada con alfabetos y * . La tarea es encontrar la string a partir de la cual se generó. La string requerida se puede generar a partir de la string codificada reemplazando todos los * con los valores de prefijo de la string codificada. 

Ejemplos:

Entrada: str = ab*c*d
Salida: “ababcababcd”
Explicación: Para la primera aparición de   “*” , “ab” es el prefijo. Entonces, ‘*’ se reemplaza por «ab», lo que da como resultado que la string sea «ababc*d»  y para el siguiente ‘ * ‘ el prefijo es «ababc». Entonces la string ahora cambiará de «ababc*d» a «ababcababcd».

Entrada:   str = “z*z*z”
Salida:   zzzzzzz

Enfoque: La solución se basa en el enfoque codicioso . Siga los pasos que se mencionan a continuación para resolver el problema:

• Considere un resultado de string vacía .
• Iterar sobre la string codificada dada.
  • si el carácter actual en la string no es «*» , agregue el carácter actual al resultado .
  • De lo contrario, si el carácter actual es «*», agregue la string de resultado formada hasta ahora con ella misma .
• Devuelve el resultado.

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

// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to return a string
// found from the coded string
string findstring(string str)
{
    // Declaring string to store result
    string result = "";
  
    // Loop to generate the original string
    for (int i = 0; str[i] != '\0'; i++) {
        // If current character in string
        // is '*' add result to itself
        if (str[i] == '*')
            result += result;
  
        // Else add current element only
        else
            result += str[i];
    }
    // Return the result
    return result;
}
  
// Driver code
int main()
{
    string str = "ab*c*d";
    cout << findstring(str);
    return 0;
}

// Java code to implement above approach
class GFG {
  
    // Function to return a string
    // found from the coded string
    static String findstring(String str)
    {
  
        // Declaring string to store result
        String result = "";
  
        // Loop to generate the original string
        for (int i = 0; i < str.length(); i++) {
  
            // If current character in string
            // is '*' add result to itself
            if (str.charAt(i) == '*')
                result += result;
  
            // Else add current element only
            else
                result += str.charAt(i);
        }
  
        // Return the result
        return result;
    }
  
    // Driver code
    public static void main(String[] args)
    {
        String str = "ab*c*d";
        System.out.println(findstring(str));
    }
}
  
// This code is contributed by ukasp.

# Python code for the above approach
  
# Function to return a string
# found from the coded string
def findstring(str):
    
    # Declaring string to store result
    result = ""
  
    # Loop to generate the original string
    for i in range(len(str)):
        
        # If current character in string
        # is '*' add result to itself
        if (str[i] == '*'):
                result += result
  
        # Else add current element only
        else:
                result += str[i]
    # Return the result
    return result
  
# Driver code
str = "ab*c*d"
print(findstring(str))
  
# This code is contributed by Saurabh Jaiswal

// C# code to implement above approach
using System;
class GFG
{
  
  // Function to return a string
  // found from the coded string
  static string findstring(string str)
  {
  
    // Declaring string to store result
    string result = "";
  
    // Loop to generate the original string
    for (int i = 0; i < str.Length; i++)
    {
  
      // If current character in string
      // is '*' add result to itself
      if (str[i] == '*')
        result += result;
  
      // Else add current element only
      else
        result += str[i];
    }
  
    // Return the result
    return result;
  }
  
  // Driver code
  public static void Main()
  {
    string str = "ab*c*d";
    Console.Write(findstring(str));
  
  }
}
  
// This code is contributed by Samim Hossain Mondal.

<script>
   // JavaScript code for the above approach
 
 
   // Function to return a string
   // found from the coded string
   function findstring(str) {
     // Declaring string to store result
     let result = "";
 
     // Loop to generate the original string
     for (let i = 0; i < str.length; i++) {
       // If current character in string
       // is '*' add result to itself
       if (str[i] == '*')
         result += result;
 
       // Else add current element only
       else
         result += str[i];
     }
     // Return the result
     return result;
   }
 
   // Driver code
 
   let str = "ab*c*d";
   document.write(findstring(str));
 
 // This code is contributed by Potta Lokesh
 </script>

ababcababcd

Complejidad temporal: O(N)
Espacio auxiliar: O(N)