Encuentre todas las strings formadas a partir de caracteres asignados a dígitos de un número

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

Deja una respuesta

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