Dada la string str, la tarea es repetir cada substring de la string X número de veces, donde X es el número compuesto por los dígitos consecutivos presentes justo después de la substring en la string original. Por ejemplo, si str = «g1e2ks1», la string resultante será «geeks».
Ejemplos:
Entrada: str = “2a10bd3”
Salida: aaaaaaaaaabdbdbd
Explicación: El primer dígito “2” no es necesario ya que no hay una substring válida antes. El carácter «a» se repetirá 10 veces y luego «bd» se repetirá tres veces.Entrada: str = «g1e2ks1for1g1e2ks1»
Salida: geeksforgeeks
Aquí se ha discutido un enfoque iterativo de este problema . Este artículo se centra en un enfoque recursivo para resolver el problema dado.
Enfoque: recorrer la string carácter por carácter recursivamente. Mientras atraviesa, mantenga los caracteres en una string separada y los dígitos que representan el número de repeticiones en un número entero. Para cada conjunto de dígitos encontrado, agregue las ocurrencias de la string almacenada de acuerdo con el número entero encontrado en una string resultante final y llame recursivamente a la string restante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Stores the final string
string res = "";
// Recursive function to generate
// the required string
void decode(string s, int i, string t, int x)
{
// If complete string has
// been traversed
if (i == s.length()) {
// Append string t, s times
for (int i = 0; i < x; i++)
res = res + t;
return;
}
// If current character
// is an integer
if (isdigit(s[i]) && !t.empty()) {
x = x * 10 + (s[i] - '0');
}
// If current character
// in an alphabet
if (!isdigit(s[i])) {
if (!t.empty() && x > 0) {
// Append t, x times
for (int i = 0; i < x; i++)
res = res + t;
// Update the value
// of t and x
t = "";
x = 0;
}
t = t + s[i];
}
// Recursive call for the
// remaining string
decode(s, i + 1, t, x);
}
// Function to convert the given
// string into desired form
string decodeString(string s)
{
// Recursive Call
decode(s, 0, "", 0);
// Return Answer
return res;
}
// Driven Program
int main()
{
string str = "g1e2k1s1for1g1e2ks1";
cout << decodeString(str);
return 0;
}
Java
// Java program of the above approach
import java.util.*;
class GFG
{
// Stores the final String
static String res = "";
// Recursive function to generate
// the required String
static void decode(String s, int i, String t, int x)
{
// If complete String has
// been traversed
if (i == s.length()) {
// Append String t, s times
for (int j = 0; j < x; j++)
res = res + t;
return;
}
// If current character
// is an integer
if (Character.isDigit(s.charAt(i)) && !t.isEmpty()) {
x = x * 10 + (s.charAt(i) - '0');
}
// If current character
// in an alphabet
if (!Character.isDigit(s.charAt(i))) {
if (!t.isEmpty() && x > 0) {
// Append t, x times
for (int j = 0; j < x; j++)
res = res + t;
// Update the value
// of t and x
t = "";
x = 0;
}
t = t + s.charAt(i);
}
// Recursive call for the
// remaining String
decode(s, i + 1, t, x);
}
// Function to convert the given
// String into desired form
static String decodeString(String s)
{
// Recursive Call
decode(s, 0, "", 0);
// Return Answer
return res;
}
// Driven Program
public static void main(String[] args)
{
String str = "g1e2k1s1for1g1e2ks1";
System.out.print(decodeString(str));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program of the above approach
# Stores the final String
res = "";
# Recursive function to generate
# the required String
def decode(s, i, t, x):
global res;
# If complete String has
# been traversed
if (i == len(s)):
# Append String t, s times
for j in range(x):
res = res + t;
return;
# If current character
# is an integer
if (s[i].isdigit() and len(t)!=0):
x = x * 10 + (ord(s[i]) - ord('0'));
# If current character
# in an alphabet
if (s[i].isdigit()==False):
if (len(t)!=0 and x > 0):
# Append t, x times
for j in range(x):
res = res + t;
# Update the value
# of t and x
t = "";
x = 0;
t = t + s[i];
# Recursive call for the
# remaining String
decode(s, i + 1, t, x);
# Function to convert the given
# String into desired form
def decodeString(s):
# Recursive Call
decode(s, 0, "", 0);
# Return Answer
return res;
# Driven Program
if __name__ == '__main__':
str = "g1e2k1s1for1g1e2ks1";
print(decodeString(str));
# This code is contributed by 29AjayKumar
C#
// C# program of the above approach
using System;
public class GFG
{
// Stores the readonly String
static String res = "";
// Recursive function to generate
// the required String
static void decode(String s, int i, String t, int x)
{
// If complete String has
// been traversed
if (i == s.Length) {
// Append String t, s times
for (int j = 0; j < x; j++)
res = res + t;
return;
}
// If current character
// is an integer
if (char.IsDigit(s[i]) && t.Length!=0) {
x = x * 10 + (s[i] - '0');
}
// If current character
// in an alphabet
if (!char.IsDigit(s[i])) {
if (t.Length!=0 && x > 0) {
// Append t, x times
for (int j = 0; j < x; j++)
res = res + t;
// Update the value
// of t and x
t = "";
x = 0;
}
t = t + s[i];
}
// Recursive call for the
// remaining String
decode(s, i + 1, t, x);
}
// Function to convert the given
// String into desired form
static String decodeString(String s)
{
// Recursive Call
decode(s, 0, "", 0);
// Return Answer
return res;
}
// Driven Program
public static void Main(String[] args)
{
String str = "g1e2k1s1for1g1e2ks1";
Console.Write(decodeString(str));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript code for the above approach
// Stores the final string
var res = "";
// Recursive function to generate
// the required string
function decode(s, i, t, x)
{
// If complete string has
// been traversed
if (i == s.length) {
// Append string t, s times
for (let i = 0; i < x; i++)
res = res + t;
return;
}
// If current character
// is an integer
if (Number.isInteger(parseInt(s[i])) && t.length != 0) {
x = x * 10 + (s[i].charCodeAt(0) - '0'.charCodeAt(0));
}
// If current character
// in an alphabet
if (!Number.isInteger(parseInt(s[i]))) {
if (!t.length == 0 && x > 0) {
// Append t, x times
for (let i = 0; i < x; i++)
res = res + t;
// Update the value
// of t and x
t = "";
x = 0;
}
t = t + s[i];
}
// Recursive call for the
// remaining string
decode(s, i + 1, t, x);
}
// Function to convert the given
// string into desired form
function decodeString(s)
{
// Recursive Call
decode(s, 0, "", 0);
// Return Answer
return res;
}
// Driven Program
let str = "g1e2k1s1for1g1e2ks1";
document.write(decodeString(str));
// This code is contributed by Potta Lokesh
</script>
Producción
geeksforgeeks
Complejidad de tiempo: O(M), donde M es la suma de todos los números enteros presentes en la string dada
Espacio auxiliar: O(N)