Considere la siguiente lista donde cada dígito del 1 al 9 se asigna a unos pocos caracteres.
1 -> ['A', 'B', 'C'] 2 -> ['D', 'E', 'F'] 3 -> ['G', 'H', 'I'] 4 -> ['J', 'K', 'L'] 5 -> ['M', 'N', 'O'] 6 -> ['P', 'Q', 'R'] 7 -> ['S', 'T', 'U'] 8 -> ['V', 'W', 'X'] 9 -> ['Y', 'Z']
Dado un número, reemplaza sus dígitos con los caracteres correspondientes en la lista dada e imprime todas las strings posibles. Se debe considerar el mismo carácter para cada aparición de un dígito en el número. El número de entrada es positivo y no contiene 0. Ejemplos:
Input : 121 Output : ADA BDB CDC AEA BEB CEC AFA BFB CFC Input : 22 Output : DD EE FF
La idea es que para cada dígito en el número de entrada, consideramos strings formadas por el dígito anterior y les agregamos caracteres asignados al dígito actual. Si esta no es la primera aparición del dígito, agregamos el mismo carácter que se usó en su primera aparición.
Implementación:
C++
// C++ program to find all strings formed from a given
// number where each digit maps to given characters.
#include <bits/stdc++.h>
using namespace std;
// Function to find all strings formed from a given
// number where each digit maps to given characters.
vector<string> findCombinations(vector<int> input,
vector<char> table[])
{
// vector of strings to store output
vector<string> out, temp;
// stores index of first occurrence
// of the digits in input
unordered_map<int, int> mp;
// maintains index of current digit considered
int index = 0;
// for each digit
for (int d: input)
{
// store index of first occurrence
// of the digit in the map
if (mp.find(d) == mp.end())
mp[d] = index;
// clear vector contents for future use
temp.clear();
// do for each character that maps to the digit
for (int i = 0; i < table[d - 1].size(); i++)
{
// for first digit, simply push all its
// mapped characters in the output list
if (index == 0)
{
string s(1, table[d - 1].at(i));
out.push_back(s);
}
// from second digit onwards
if (index > 0)
{
// for each string in output list
// append current character to it.
for(string str: out)
{
// convert current character to string
string s(1, table[d - 1].at(i));
// Imp - If this is not the first occurrence
// of the digit, use same character as used
// in its first occurrence
if(mp[d] != index)
s = str[mp[d]];
str = str + s;
// store strings formed by current digit
temp.push_back(str);
}
// nothing more needed to be done if this
// is not the first occurrence of the digit
if(mp[d] != index)
break;
}
}
// replace contents of output list with temp list
if(index > 0)
out = temp;
index++;
}
return out;
}
// Driver program
int main()
{
// vector to store the mappings
vector<char> table[] =
{
{ 'A', 'B', 'C' },
{ 'D', 'E', 'F' },
{ 'G', 'H', 'I' },
{ 'J', 'K', 'L' },
{ 'M', 'N', 'O' },
{ 'P', 'Q', 'R' },
{ 'S', 'T', 'U' },
{ 'V', 'W', 'X' },
{ 'Y', 'Z' }
};
// vector to store input number
vector<int> input = { 1, 2, 1};
vector<string> out = findCombinations(input, table);
// print all possible strings
for (string it: out)
cout << it << " ";
return 0;
}
Python3
# Python program to find all strings formed from a given # number where each digit maps to given characters. # Function to find all strings formed from a given # number where each digit maps to given characters. def findCombinations(input: list, table: list) -> list: # vector of strings to store output out, temp = [], [] # stores index of first occurrence # of the digits in input mp = dict() # maintains index of current digit considered index = 0 # for each digit for d in input: # store index of first occurrence # of the digit in the map if d not in mp: mp[d] = index # clear vector contents for future use temp.clear() # do for each character that maps to the digit for i in range(len(table[d - 1])): # for first digit, simply push all its # mapped characters in the output list if index == 0: s = table[d - 1][i] out.append(s) # from second digit onwards if index > 0: # for each string in output list # append current character to it. for string in out: # convert current character to string s = table[d - 1][i] # Imp - If this is not the first occurrence # of the digit, use same character as used # in its first occurrence if mp[d] != index: s = string[mp[d]] string = string + s # store strings formed by current digit temp.append(string) # nothing more needed to be done if this # is not the first occurrence of the digit if mp[d] != index: break # replace contents of output list with temp list if index > 0: out = temp.copy() index += 1 return out # Driver Code if __name__ == "__main__": # vector to store the mappings table = [['A', 'B', 'C'], ['D', 'E', 'F'], ['G', 'H', 'I'], ['J', 'K', 'L'], ['M', 'N', 'O'], ['P', 'Q', 'R'], ['S', 'T', 'U'], ['V', 'W', 'X'], ['Y', 'Z']] # vector to store input number input = [1, 2, 1] out = findCombinations(input, table) # print all possible strings for it in out: print(it, end=" ") # This code is contributed by # sanjeev2552
Javascript
<script>
// JavaScript program to find all strings formed from a given
// number where each digit maps to given characters.
// Function to find all strings formed from a given
// number where each digit maps to given characters.
function findCombinations(input,table)
{
// vector of strings to store output
let out = [], temp = [];
// stores index of first occurrence
// of the digits in input
let mp = new Map();
// maintains index of current digit considered
let index = 0;
// for each digit
for (let d of input)
{
// store index of first occurrence
// of the digit in the map
if (mp.has(d) == false)
mp.set(d , index);
// clear vector contents for future use
temp = [];
// do for each character that maps to the digit
for (let i = 0; i < table[d - 1].length; i++)
{
// for first digit, simply push all its
// mapped characters in the output list
if (index == 0)
{
let s = table[d - 1][i];
out.push(s);
}
// from second digit onwards
if (index > 0)
{
// for each string in output list
// append current character to it.
for(let str of out)
{
// convert current character to string
let s = table[d - 1][i];
// Imp - If this is not the first occurrence
// of the digit, use same character as used
// in its first occurrence
if(mp.get(d) != index)
s = str[mp.get(d)];
str = str + s;
// store strings formed by current digit
temp.push(str);
}
// nothing more needed to be done if this
// is not the first occurrence of the digit
if(mp.get(d) != index)
break;
}
}
// replace contents of output list with temp list
if(index > 0)
out = temp;
index++;
}
return out;
}
// Driver program
// vector to store the mappings
let table = [
[ 'A', 'B', 'C' ],
[ 'D', 'E', 'F' ],
[ 'G', 'H', 'I' ],
[ 'J', 'K', 'L' ],
[ 'M', 'N', 'O' ],
[ 'P', 'Q', 'R' ],
[ 'S', 'T', 'U' ],
[ 'V', 'W', 'X' ],
[ 'Y', 'Z' ]
];
// vector to store input number
let input = [ 1, 2, 1 ];
let out = findCombinations(input, table);
// print all possible strings
for (let it of out)
document.write(it , " ");
// This code is contributed by shinjanpatra
</script>
Producción
ADA BDB CDC AEA BEB CEC AFA BFB CFC
Este artículo es una contribución de Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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