Dado un número, encuentre todas las asignaciones posibles de los caracteres en orden ordenado.
Ejemplos:
Input: 123
Output: ABC
AW
LC
Explanation:
1 = A; 2 = B; 3 = C; 12 = L; 23 = W
{1, 2, 3}
/ \
/ \
"A"{2, 3} "L"{3}
/ \ / \
/ \ / \
"AB"{3} "A"{23} "LC" null
/ \ / \
/ \ / \
"ABC" null "AW" null
Input : 2122
Output : BABB
BAV
BLB
UBB
UV
Acercarse :
- Se crea una función recursiva que toma una array de caracteres de entrada que contiene el número almacenado en forma de caracteres, una array de caracteres de salida y dos variables (por ejemplo, i y j) que se pueden usar para iterar sobre ambas arrays.
- Usando la recursión, se obtiene el carácter para el i -ésimo dígito en la array de entrada y el carácter asignado correspondiente con ese dígito se almacena en el j -ésimo índice en la array de salida.
- Habrá dos llamadas recursivas. La primera llamada procesará un solo dígito cada vez, mientras que la segunda llamada procesará dos dígitos a la vez.
- Al procesar dos dígitos a la vez, el número debe ser siempre menor que 26 porque después de combinar, el carácter correspondiente debe estar entre la A y la Z.
- Por último, en el caso base, cuando se ha procesado toda la string de entrada, se imprime la array de salida.
A continuación se muestra la implementación del enfoque anterior.
CPP
// C++ program to find all the possible
// string mappings of a given number
// in a sorted order
#include <bits/stdc++.h>
using namespace std;
// Function to find the string mappings
void mapped(char inputarr[], char outputarr[],
int i, int j)
{
// Base case
if (inputarr[i] == '\0') {
outputarr[j] = '\0';
cout << outputarr << endl;
return;
}
// Convert the character to integer
int digit = inputarr[i] - '0';
// To store the characters corresponding
// to the digits which are further
// stored in outputarr[]
char ch = digit + 'A' - 1;
outputarr[j] = ch;
// First recursive call taking one digit at a time
mapped(inputarr, outputarr, i + 1, j + 1);
if (inputarr[i + 1] != '\0') {
int second_digit = inputarr[i + 1] - '0';
int number = digit * 10 + second_digit;
if (number <= 26) {
ch = number + 'A' - 1;
outputarr[j] = ch;
// Second recursive call processing
// two digits at a time
mapped(inputarr, outputarr, i + 2, j + 1);
}
}
}
// Driver code
int main()
{
char inputarr[] = { '1', '2', '3' };
int m = pow(2, 3) - 1;
int n = sizeof(m) / sizeof(int);
char outputarr[n];
mapped(inputarr, outputarr, 0, 0);
return 0;
}
Java
// Java program to find all the possible
// string mappings of a given number
// in a sorted order
class GFG
{
// Function to find the string mappings
static void mapped(char inputarr[], char outputarr[],
int i, int j)
{
// Base case
if (i >= inputarr.length)
{
String str = new String(outputarr);
System.out.println(str.substring(0, j));
return;
}
// Convert the character to integer
int digit = inputarr[i] - '0';
// To store the characters corresponding
// to the digits which are further
// stored in outputarr[]
char ch = (char)(digit + (int)('A') - 1);
outputarr[j] = ch;
// First recursive call taking one digit at a time
mapped(inputarr, outputarr, i + 1, j + 1);
if (i + 1 < inputarr.length)
{
int second_digit = inputarr[i + 1] - '0';
int number = digit * 10 + second_digit;
if (number <= 26)
{
ch = (char)(number + (int)'A' - 1);
outputarr[j] = ch;
// Second recursive call processing
// two digits at a time
mapped(inputarr, outputarr, i + 2, j + 1);
}
}
}
// Driver code
public static void main (String[] args)
{
char inputarr[] = { '1', '2', '3' };
int m = (int)Math.pow(2, 3) - 1;
int n = 1;
char outputarr[] = new char[m];
mapped(inputarr, outputarr, 0, 0);
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 program to find all the possible
# string mappings of a given number
# in a sorted order
# Function to find the string mappings
def mapped(inputarr, outputarr, i, j):
# Base case
if (i == len(inputarr)):
print("".join(outputarr[:j]))
return
# Convert the character to integer
digit = ord(inputarr[i]) - ord('0')
# To store the characters corresponding
# to the digits which are further
# stored in outputarr[]
ch = digit + ord('A') - 1
outputarr[j] = chr(ch)
# First recursive call taking one digit at a time
mapped(inputarr, outputarr, i + 1, j + 1)
if (i + 1 < len(inputarr) and [i + 1] != '\0'):
second_digit = ord(inputarr[i + 1]) - ord('0')
number = digit * 10 + second_digit
if (number <= 26):
ch = number + ord('A') - 1
outputarr[j] = chr(ch)
# Second recursive call processing
# two digits at a time
mapped(inputarr, outputarr, i + 2, j + 1)
# Driver code
inputarr = ['1', '2', '3']
m = pow(2, 3) - 1
n = 1
outputarr = ['0'] * m
mapped(inputarr, outputarr, 0, 0)
# This code is contributed by mohit kumar 29
C#
// C# program to find all the possible
// string mappings of a given number
// in a sorted order
using System;
class GFG
{
// Function to find the string mappings
static void mapped(char []inputarr, char []outputarr,
int i, int j)
{
// Base case
if (i >= inputarr.Length)
{
string str = new string(outputarr);
Console.WriteLine(str.Substring(0, j));
return;
}
// Convert the character to integer
int digit = inputarr[i] - '0';
// To store the characters corresponding
// to the digits which are further
// stored in outputarr[]
char ch = (char)(digit + (int)('A') - 1);
outputarr[j] = ch;
// First recursive call taking one digit at a time
mapped(inputarr, outputarr, i + 1, j + 1);
if (i + 1 < inputarr.Length)
{
int second_digit = inputarr[i + 1] - '0';
int number = digit * 10 + second_digit;
if (number <= 26)
{
ch = (char)(number + (int)'A' - 1);
outputarr[j] = ch;
// Second recursive call processing
// two digits at a time
mapped(inputarr, outputarr, i + 2, j + 1);
}
}
}
// Driver code
public static void Main ()
{
char []inputarr = { '1', '2', '3' };
int m = (int)Math.Pow(2, 3) - 1;
int n = 1;
char []outputarr = new char[m];
mapped(inputarr, outputarr, 0, 0);
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// JavaScript program to find all the possible
// string mappings of a given number
// in a sorted order
// Function to find the string mappings
function mapped(inputarr,outputarr,i,j)
{
// Base case
if (i >= inputarr.length)
{
let str = (outputarr).join("");
document.write(str.substring(0, j)+"<br>");
return;
}
// Convert the character to integer
let digit = inputarr[i].charCodeAt(0) -
'0'.charCodeAt(0);
// To store the characters corresponding
// to the digits which are further
// stored in outputarr[]
let ch =
String.fromCharCode(digit + ('A').charCodeAt(0) - 1);
outputarr[j] = ch;
// First recursive call taking one digit at a time
mapped(inputarr, outputarr, i + 1, j + 1);
if (i + 1 < inputarr.length)
{
let second_digit = inputarr[i + 1].charCodeAt(0) -
'0'.charCodeAt(0);
let number = digit * 10 + second_digit;
if (number <= 26)
{
ch =
String.fromCharCode(number + 'A'.charCodeAt(0) - 1);
outputarr[j] = ch;
// Second recursive call processing
// two digits at a time
mapped(inputarr, outputarr, i + 2, j + 1);
}
}
}
// Driver code
let inputarr=['1', '2', '3'];
let m = Math.pow(2, 3) - 1;
let n = 1;
let outputarr = new Array(m);
mapped(inputarr, outputarr, 0, 0);
// This code is contributed by patel2127
</script>
Producción:
ABC AW LC
Publicación traducida automáticamente
Artículo escrito por mishrakishan1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA