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++
// 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
// 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.
Python3
# 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#
// 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.
Javascript
<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)
Publicación traducida automáticamente
Artículo escrito por harshalkhond y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA