Considere un sistema de codificación de alfabetos a números enteros donde ‘a’ se representa como 1, ‘b’ como 2, .. ‘z’ como 26. Dada una array de dígitos (1 a 9) como entrada, escriba una función que imprima todos interpretaciones válidas de la array de entrada.
Ejemplos
Input: {1, 1}
Output: ("aa", 'k")
[2 interpretations: aa(1, 1), k(11)]
Input: {1, 2, 1}
Output: ("aba", "au", "la")
[3 interpretations: aba(1,2,1), au(1,21), la(12,1)]
Input: {9, 1, 8}
Output: {"iah", "ir"}
[2 interpretations: iah(9,1,8), ir(9,18)]
Tenga en cuenta que no podemos cambiar el orden de la array. Eso significa que {1,2,1} no puede convertirse en {2,1,1}
A primera vista parece un problema de permutación/combinación. Pero al mirar más de cerca, se dará cuenta de que este es un problema de árbol interesante.
La idea aquí es que la string puede tomar como máximo dos caminos:
1. Procesar un solo dígito
2. Procesar dos dígitos
Eso significa que podemos usar un árbol binario aquí. El procesamiento con un solo dígito será el hijo izquierdo y el de dos dígitos será el hijo derecho. Si el valor de dos dígitos es mayor que 26, nuestro hijo derecho será nulo ya que no tenemos un alfabeto para más de 26.
Entendamos con un ejemplo. Array a = {1,2,1}. El siguiente diagrama muestra cómo crece nuestro árbol.
“” {1,2,1} Codes used in tree
/ \ "a" --> 1
/ \ "b" --> 2
"a"{2,1} "l"{1} "l" --> 12
/ \ / \
/ \ / \
"ab"{1} "au" "la" null
/ \
/ \
"aba" null
Las llaves {} contienen una array aún pendiente de procesamiento. Tenga en cuenta que con cada nivel, el tamaño de nuestra array disminuye. Si observa detenidamente, no es difícil encontrar que la altura del árbol siempre es n (tamaño de array)
¿Cómo imprimir todas las strings (interpretaciones)? Las strings de salida son el Node hoja del árbol. es decir, para {1,2,1}, la salida es {aba au la}.
Podemos concluir que hay principalmente dos pasos para imprimir todas las interpretaciones de una array de enteros dada.
Paso 1: Cree un árbol binario con todas las interpretaciones posibles en los Nodes hoja.
Paso 2: imprima todos los Nodes hoja del árbol binario creado en el paso 1.
A continuación se muestra la implementación de Java del algoritmo anterior.
Java
// A Java program to print all interpretations of an integer array
import java.util.Arrays;
// A Binary Tree node
class Node {
String dataString;
Node left;
Node right;
Node(String dataString) {
this.dataString = dataString;
//Be default left and right child are null.
}
public String getDataString() {
return dataString;
}
}
public class arrayToAllInterpretations {
// Method to create a binary tree which stores all interpretations
// of arr[] in lead nodes
public static Node createTree(int data, String pString, int[] arr) {
// Invalid input as alphabets maps from 1 to 26
if (data > 26)
return null;
// Parent String + String for this node
String dataToStr = pString + alphabet[data];
Node root = new Node(dataToStr);
// if arr.length is 0 means we are done
if (arr.length != 0) {
data = arr[0];
// new array will be from index 1 to end as we are consuming
// first index with this node
int newArr[] = Arrays.copyOfRange(arr, 1, arr.length);
// left child
root.left = createTree(data, dataToStr, newArr);
// right child will be null if size of array is 0 or 1
if (arr.length > 1) {
data = arr[0] * 10 + arr[1];
// new array will be from index 2 to end as we
// are consuming first two index with this node
newArr = Arrays.copyOfRange(arr, 2, arr.length);
root.right = createTree(data, dataToStr, newArr);
}
}
return root;
}
// To print out leaf nodes
public static void printleaf(Node root) {
if (root == null)
return;
if (root.left == null && root.right == null)
System.out.print(root.getDataString() + " ");
printleaf(root.left);
printleaf(root.right);
}
// The main function that prints all interpretations of array
static void printAllInterpretations(int[] arr) {
// Step 1: Create Tree
Node root = createTree(0, "", arr);
// Step 2: Print Leaf nodes
printleaf(root);
System.out.println(); // Print new line
}
// For simplicity I am taking it as string array. Char Array will save space
private static final String[] alphabet = {"", "a", "b", "c", "d", "e",
"f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r",
"s", "t", "u", "v", "w", "x", "v", "z"};
// Driver method to test above methods
public static void main(String args[]) {
// aacd(1,1,3,4) amd(1,13,4) kcd(11,3,4)
// Note : 1,1,34 is not valid as we don't have values corresponding
// to 34 in alphabet
int[] arr = {1, 1, 3, 4};
printAllInterpretations(arr);
// aaa(1,1,1) ak(1,11) ka(11,1)
int[] arr2 = {1, 1, 1};
printAllInterpretations(arr2);
// bf(2,6) z(26)
int[] arr3 = {2, 6};
printAllInterpretations(arr3);
// ab(1,2), l(12)
int[] arr4 = {1, 2};
printAllInterpretations(arr4);
// a(1,0} j(10)
int[] arr5 = {1, 0};
printAllInterpretations(arr5);
// "" empty string output as array is empty
int[] arr6 = {};
printAllInterpretations(arr6);
// abba abu ava lba lu
int[] arr7 = {1, 2, 2, 1};
printAllInterpretations(arr7);
}
}
Producción:
aacd amd kcd aaa ak ka bf z ab l a j abba abu ava lba lu
Ejercicio:
1. ¿Cuál es la complejidad temporal de esta solución? [Sugerencia: tamaño del árbol + búsqueda de Nodes de hoja]
2. ¿Podemos almacenar Nodes de hoja en el momento de la creación del árbol para que no sea necesario ejecutar el bucle nuevamente para obtener el Node de hoja?
3. ¿Cómo podemos reducir el espacio adicional?
Este artículo está compilado por Varun Jain . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Método 2: (usando retroceso)
Este problema se puede resolver utilizando backtracking. Una de las intuiciones básicas es que todos los números que vamos a generar usando los dígitos de la array de entrada deben estar entre el rango de [1, 26] ambos inclusive. Entonces, de una manera de fuerza bruta, probamos todas las combinaciones posibles y si el número generado hasta ahora se encuentra entre el rango de [1, 26], agregamos el alfabeto correspondiente y recurrimos para la string restante y extraemos el carácter adjunto (retroceder) para encontrar todas las interpretaciones válidas. En este proceso, si llegamos al final de la string, significa que hemos encontrado 1 interpretación posible. Pero en cualquier momento, si encontramos que el número generado hasta ahora es mayor que 26, no necesitamos continuar porque ese no es un número válido para interpretar, así que en ese caso retrocedemos e intentamos con el resto de las combinaciones.
A continuación se muestra la implementación de C++
C++
#include<bits/stdc++.h>
using namespace std;
string dup;
// function which returns all the valid interpretations
void compute(int arr[],int n,vector<string> &vect,int s)
{
//cout << "ex" << endl;
/*
if we reach the end of the string
than we have found 1 valid interpretation
*/
if(s == n)
{
// store it in the vector
vect.push_back(dup);
/*
since we have reached the end of the string
there is no string to recur so return
*/
return ;
}
// initialize the num with zero
int num = 0;
for(int i=s;i<n;i++)
{
// generate the number
num = num*10 + arr[i];
/*
validate the number generated so far
*/
if(num >= 1 and num <= 26)
{
// append the corresponding alphabet
dup += ('a' + (num - 1));
// recur for the remaining string
compute(arr,n,vect,i+1);
// backtrack to find rest of the combinations
dup.pop_back();
}
// if the number generated so far if greater
// than 26 we need not to proceed further
// as it cannot be used to make a valid
// interpretation
else
break;
}
return ;
}
vector<string> findAllInterpretations(int n,int arr[])
{
// vector to store all the valid interpretations
vector<string> vect;
dup = "";
compute(arr,n,vect,0);
// return all valid interpretations
return vect;
}
int main()
{
int n;
cin >> n;
int *arr = new int[n];
for(int i=0;i<n;i++)
{
cin >> arr[i];
}
vector<string> res;
res = findAllInterpretations(n,arr);
int m = res.size();
for(int i=0;i<m;i++)
{
cout << res[i] << " ";
}
return 0;
}
Input : 5 1 1 2 1 2
Output : aabab aabl aaub alab all kbab kbl kub
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA