Encuentre todas las strings en el orden lexicográfico posible reemplazando los dígitos con ‘x’, ‘y’ o ‘z’

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

Deja una respuesta

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