Dada una string str , que consta de alfabetos ingleses en minúsculas y dígitos (0-9), la tarea es imprimir todas las strings posibles en orden lexicográfico que se pueden formar reemplazando cada aparición de un dígito con ‘ x ‘, ‘ y ‘ o ‘ z ‘.
Ejemplo:
Entrada: str = “a1b2”
Salida: axbx axby axbz aybx ayby aybz azbx azbx azby azbz
Explicación: Estas strings son las 9 strings posibles impresas en orden lexicográfico que se pueden formar a partir de “a1b2” reemplazando todos los dígitos con ‘x’, ‘ y’ o ‘z’.Entrada: str = “abcdef”
Salida: abcdef
Enfoque: El problema dado se puede resolver usando recursividad con la ayuda de backtracking . La idea es crear una función recursiva y, mientras se itera la string dada, reemplazar cada aparición de un dígito con ‘ x ‘, ‘ y ‘ y ‘ z ‘ y llamar recursivamente a la string restante para cada una de las tres strings.
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;
// Recursive function to print all
// the possible strings after replacing
// the digits, in lexicographic order
void allPossibleStrings(
string str, string cur, int i)
{
// If the complete string
// has been traversed
if (str.size() == cur.size()) {
// Print current string
cout << cur << " ";
return;
}
// If current character
// is a digit
if (isdigit(str[i])) {
// Recursive call after replacing
// current character with x
allPossibleStrings(
str, cur + "x", i + 1);
// Recursive call after replacing
// current character with y
allPossibleStrings(
str, cur + "y", i + 1);
// Recursive call after replacing
// current character with z
allPossibleStrings(
str, cur + "z", i + 1);
}
else {
// Recursive call after appending
// the current character
allPossibleStrings(
str, cur + str[i], i + 1);
}
}
// Driver Code
int main()
{
string str = "a1b2";
allPossibleStrings(str, "", 0);
return 0;
}
Java
// Java program of the above approach
class GFG {
// Recursive function to print all
// the possible Strings after replacing
// the digits, in lexicographic order
static void allPossibleStrings(
String str, String cur, int i) {
// If the complete String
// has been traversed
if (str.length() == cur.length()) {
// Print current String
System.out.print(cur + " ");
return;
}
// If current character
// is a digit
if (Character.isDigit(str.charAt(i))) {
// Recursive call after replacing
// current character with x
allPossibleStrings(
str, cur + "x", i + 1);
// Recursive call after replacing
// current character with y
allPossibleStrings(
str, cur + "y", i + 1);
// Recursive call after replacing
// current character with z
allPossibleStrings(
str, cur + "z", i + 1);
} else {
// Recursive call after appending
// the current character
allPossibleStrings(
str, cur + str.charAt(i), i + 1);
}
}
// Driver Code
public static void main(String args[]) {
String str = "a1b2";
allPossibleStrings(str, "", 0);
}
}
// This code is contributed by Saurabh Jaiswal
Python3
# python3 program of the above approach # Recursive function to print all # the possible strings after replacing # the digits, in lexicographic order def allPossibleStrings(str, cur, i): # If the complete string # has been traversed if (len(str) == len(cur)): # Print current string print(cur, end=" ") return # If current character # is a digit if (str[i] >= '0' and str[i] <= '9'): # Recursive call after replacing # current character with x allPossibleStrings(str, cur + "x", i + 1) # Recursive call after replacing # current character with y allPossibleStrings(str, cur + "y", i + 1) # Recursive call after replacing # current character with z allPossibleStrings(str, cur + "z", i + 1) else: # Recursive call after appending # the current character allPossibleStrings(str, cur + str[i], i + 1) # Driver Code if __name__ == "__main__": str = "a1b2" allPossibleStrings(str, "", 0) # This code is contributed by rakeshsahni
C#
// C# program of the above approach
using System;
class GFG
{
// Recursive function to print all
// the possible strings after replacing
// the digits, in lexicographic order
static void allPossibleStrings(
string str, string cur, int i)
{
// If the complete string
// has been traversed
if (str.Length == cur.Length) {
// Print current string
Console.Write(cur + " ");
return;
}
// If current character
// is a digit
if (Char.IsDigit(str[i])) {
// Recursive call after replacing
// current character with x
allPossibleStrings(
str, cur + "x", i + 1);
// Recursive call after replacing
// current character with y
allPossibleStrings(
str, cur + "y", i + 1);
// Recursive call after replacing
// current character with z
allPossibleStrings(
str, cur + "z", i + 1);
}
else {
// Recursive call after appending
// the current character
allPossibleStrings(
str, cur + str[i], i + 1);
}
}
// Driver Code
public static void Main()
{
string str = "a1b2";
allPossibleStrings(str, "", 0);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Recursive function to print all
// the possible strings after replacing
// the digits, in lexicographic order
function allPossibleStrings(
str, cur, i) {
// If the complete string
// has been traversed
if (str.length == cur.length) {
// Print current string
document.write(cur + " ");
return;
}
// If current character
// is a digit
if (Number.isInteger(parseInt(str[i]))) {
// Recursive call after replacing
// current character with x
allPossibleStrings(
str, cur + "x", i + 1);
// Recursive call after replacing
// current character with y
allPossibleStrings(
str, cur + "y", i + 1);
// Recursive call after replacing
// current character with z
allPossibleStrings(
str, cur + "z", i + 1);
}
else {
// Recursive call after appending
// the current character
allPossibleStrings(
str, cur + str[i], i + 1);
}
}
// Driver Code
let str = "a1b2";
allPossibleStrings(str, "", 0);
// This code is contributed by Potta Lokesh
</script>
Producción
axbx axby axbz aybx ayby aybz azbx azby azbz
Complejidad de Tiempo: O(3 N )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por garg231978 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA