Generación de combinaciones de letras con teclados numéricos en C++

Cursos Empresas Blog Live Conf Precios

Contenido del curso

Introducción

DFS

BFS

Backtrack

Próximos pasos

Tomar examen

Generación de combinaciones de letras con teclados numéricos en C++

Resumen

¿Cómo implementar una solución en C++ para generar combinaciones de letras a partir de números?

Al crear soluciones de software, encontrar la mejor manera de implementar nuestros algoritmos es crucial. En este caso, vamos a explorar cómo desarrollar un programa en C++ que genere todas las combinaciones posibles de letras a partir de una secuencia de números, similar a los teclados de los viejos teléfonos celulares. Comencemos directamente por crear las bases, utilizando C++ para implementarlo, pero recuerda que puedes seguir estos pasos en cualquier lenguaje de programación de tu elección.

¿Cómo estructurar la relación entre números y letras?

Es fundamental poder mapear cada número a sus correspondientes letras para generar combinaciones. Para lograr esto:

Crear un unordered_map en C++: Este mapa asociará cada número a sus respectivas letras.
Llenar el mapa con cada número y su grupo de letras correspondiente.

Aquí está el código necesario en C++:

#include <unordered_map>
#include <vector>
#include <string>

std::unordered_map<char, std::string> teclado = {
    {'2', "ABC"}, {'3', "DEF"}, {'4', "GHI"},
    {'5', "JKL"}, {'6', "MNO"}, {'7', "PQRS"},
    {'8', "TUV"}, {'9', "WXYZ"}
};

Este segmento de código establece una relación clara y directa entre números y letras, lo cual es esencial para el siguiente paso de generar las combinaciones.

¿Cómo generar todas las combinaciones de letras?

La tarea principal es crear un algoritmo que pasará por cada dígito del número y generará todas las combinaciones posibles de letras. Usaremos recursión para formar las combinaciones. La función GenerarCombinaciones será la encargada de esto:

void GenerarCombinaciones(int indice, const std::string& numeroCelular, std::string palabraActual, std::vector<std::string>& listaDePalabras) {
    if (indice == numeroCelular.length()) {
        if (!palabraActual.empty()) {
            listaDePalabras.push_back(palabraActual);
        }
        return;
    }
    
    char digitoActual = numeroCelular[indice];
    for (char letra : teclado[digitoActual]) {
        GenerarCombinaciones(indice + 1, numeroCelular, palabraActual + letra, listaDePalabras);
    }
}

¿Qué hace cada parte de la función GenerarCombinaciones?

Caso base: Si hemos recorrido todos los dígitos, la palabra formada se agrega a nuestra lista de palabras.
Recorrido de letras: Para cada dígito actual, explora todas sus letras posibles y construye la palabra recursivamente.
Recursividad: Llama a la función para el siguiente dígito con la palabra actualizada.

¿Cómo retornar las combinaciones obtenidas?

Finalmente, necesitamos invocar nuestra función principal que configura el proceso y retorna las combinaciones generadas:

std::vector<std::string> ObtenerCombinacionesDeLetras(const std::string& numero) {
    std::vector<std::string> listaDePalabras;
    GenerarCombinaciones(0, numero, "", listaDePalabras);
    return listaDePalabras;
}

Consejos para el futuro

Experimenta con diferentes lenguajes de programación. Cada uno tiene sus peculiaridades y ventajas.
Prueba con entradas variadas para observar cómo el código maneja diferentes casos.
Calcula la complejidad del algoritmo. Es un ejercicio interesante que te ayudará a entender la eficiencia de tu solución.

Con paciencia y práctica, podrás usar estas técnicas para resolver problemas similares y cada vez más complejos. ¡No te detengas y sigue aprendiendo!

Comentarios

Edwin Uldarico Hernandez Osorio

Estudiante

Creo que el for no se va a ejecutar, debió ponerlo fuera de la llave del IF

William Velázquez

Estudiante

Cuál es la complejidad real para este caso? No veo en los comentarios la respuesta como dice la profesora

Alexis Otaño

Estudiante

O(K^n)

Donde K es la cantidad de digitos por cada numero, n la cantidad de numeros.

Complejidad exponencial

Daniel Ortiz

Estudiante

Funciono en java

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ConcurrentHashMap;

public class main {
  private static final  ConcurrentHashMap keyword = new ConcurrentHashMap<Integer, List<String>>();
  private static void combinedLetters(int index, String phone, String current, List<String> result) {
    if (index>=phone.length()) {
     if (!current.equalsIgnoreCase("")) {
         result.add(current);
     }
     return;
    }
    for (String letter : (List<String>)keyword.get(Integer.parseInt(phone.substring(index, index+1)))) {
      combinedLetters(index+1, phone, current+letter, result);
    }

  }

  public static void main(String []args) throws IOException, InterruptedException {
    keyword.put(2, List.of("a", "b", "c"));
    keyword.put(3, List.of("d", "e", "f"));
    keyword.put(4, List.of("g", "h", "i"));
    keyword.put(5, List.of("j", "k", "l"));
    keyword.put(6, List.of("m", "n", "o"));
    keyword.put(7, List.of("p", "q", "r", "s"));
    keyword.put(8, List.of("t", "u", "v"));
    keyword.put(9, List.of("w", "x", "y", "z"));
    List<String> result = new ArrayList<>();
    combinedLetters(0, "23", "", result);
    System.out.println(result);
  }

}

Manuel Juarez

Estudiante

import random
import collections
import time
from typing import List


def generate_numbers(number_length: int, list_length: int) -> List[List[int]]:
    return [[random.randint(0, 9)
             for _ in range(number_length)] for _ in range(list_length)]


def letter_combinations(phone_number):
    phone_dict = {
        1: [" "],
        2: ["a", "b", "c"],
        3: ["d", "e", "f"],
        4: ["g", "h", "i"],
        5: ["g", "h", "i"],
        6: ["m", "n", "o"],
        7: ["p", "q", "r", "s"],
        8: ["t", "u", "v"],
        9: ["w", "x", "y", "z"],
        0: ["+"]
    }
    all_combinations = []
    stack = collections.deque()
    for character in phone_dict[phone_number[0]]:
        stack.append([character])

    while stack:
        chain = stack.pop()
        phone_digit = len(chain)
        if phone_digit < len(phone_number):
            phone_dict_index = phone_number[phone_digit]
            characters = phone_dict[phone_dict_index]
            for character in characters:
                expanded_chain = chain+[character]
                stack.append(expanded_chain)
        else:
            all_combinations.append(chain)
    return all_combinations


def main():
    phone_numbers = generate_numbers(number_length=10, list_length=1)
    print(phone_numbers)
    start = time.time()
    for phone_number in phone_numbers:
        combinations = letter_combinations(phone_number)
        print(len(combinations))
    end = time.time()
    print(f"Total time: {end - start:.4f} seconds")


if __name__ == '__main__':
    main()

Miguel Angel Reyes Moreno

Estudiante

Solución en Python:


from typing import List





class Solution:

&#x20;   def letterCombinations(self, digits: str) -> List\[str]:

&#x20;       combinations = {

&#x20;           2: \['a','b','c'],

&#x20;           3: \['d','e','f'],

&#x20;           4: \['g','h','i'],

&#x20;           5: \['j','k','l'],

&#x20;           6: \['m','n','o'],

&#x20;           7: \['p','q','r','s'],

&#x20;           8: \['t','u','v'],

&#x20;           9: \['w','x','y','z']

&#x20;       }



&#x20;       result = \[]

&#x20;       mixing = \[]



&#x20;       if not digits:

&#x20;           return \[]



&#x20;       def backtrack(index):

&#x20;           if index == len(digits):

&#x20;               result.append("".join(mixing))

&#x20;               return



&#x20;           current\_digit = int(digits\[index])

&#x20;           letters = combinations\[current\_digit]



&#x20;           for letter in letters:

&#x20;               mixing.append(letter)

&#x20;               backtrack(index + 1)

&#x20;               mixing.pop()



&#x20;       backtrack(0)

&#x20;       return result





solution = Solution()

print(solution.letterCombinations("69"))

Fernando Sánchez Mejía

Estudiante

Yo utilizo C/C++ y Python. Como la profesora ya esta usando Python,por eso utilizo C/C++

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ConcurrentHashMap;

public class main {
  private static final  ConcurrentHashMap keyword = new ConcurrentHashMap<Integer, List<String>>();
  private static void combinedLetters(int index, String phone, String current, List<String> result) {
    if (index>=phone.length()) {
     if (!current.equalsIgnoreCase("")) {
         result.add(current);
     }
     return;
    }
    for (String letter : (List<String>)keyword.get(Integer.parseInt(phone.substring(index, index+1)))) {
      combinedLetters(index+1, phone, current+letter, result);
    }

  }

  public static void main(String []args) throws IOException, InterruptedException {
    keyword.put(2, List.of("a", "b", "c"));
    keyword.put(3, List.of("d", "e", "f"));
    keyword.put(4, List.of("g", "h", "i"));
    keyword.put(5, List.of("j", "k", "l"));
    keyword.put(6, List.of("m", "n", "o"));
    keyword.put(7, List.of("p", "q", "r", "s"));
    keyword.put(8, List.of("t", "u", "v"));
    keyword.put(9, List.of("w", "x", "y", "z"));
    List<String> result = new ArrayList<>();
    combinedLetters(0, "23", "", result);
    System.out.println(result);
  }

}

import random
import collections
import time
from typing import List


def generate_numbers(number_length: int, list_length: int) -> List[List[int]]:
    return [[random.randint(0, 9)
             for _ in range(number_length)] for _ in range(list_length)]


def letter_combinations(phone_number):
    phone_dict = {
        1: [" "],
        2: ["a", "b", "c"],
        3: ["d", "e", "f"],
        4: ["g", "h", "i"],
        5: ["g", "h", "i"],
        6: ["m", "n", "o"],
        7: ["p", "q", "r", "s"],
        8: ["t", "u", "v"],
        9: ["w", "x", "y", "z"],
        0: ["+"]
    }
    all_combinations = []
    stack = collections.deque()
    for character in phone_dict[phone_number[0]]:
        stack.append([character])

    while stack:
        chain = stack.pop()
        phone_digit = len(chain)
        if phone_digit < len(phone_number):
            phone_dict_index = phone_number[phone_digit]
            characters = phone_dict[phone_dict_index]
            for character in characters:
                expanded_chain = chain+[character]
                stack.append(expanded_chain)
        else:
            all_combinations.append(chain)
    return all_combinations


def main():
    phone_numbers = generate_numbers(number_length=10, list_length=1)
    print(phone_numbers)
    start = time.time()
    for phone_number in phone_numbers:
        combinations = letter_combinations(phone_number)
        print(len(combinations))
    end = time.time()
    print(f"Total time: {end - start:.4f} seconds")


if __name__ == '__main__':
    main()

from typing import List

class Solution:

&#x20;   def letterCombinations(self, digits: str) -> List\[str]:

&#x20;       combinations = {

&#x20;           2: \['a','b','c'],

&#x20;           3: \['d','e','f'],

&#x20;           4: \['g','h','i'],

&#x20;           5: \['j','k','l'],

&#x20;           6: \['m','n','o'],

&#x20;           7: \['p','q','r','s'],

&#x20;           8: \['t','u','v'],

&#x20;           9: \['w','x','y','z']

&#x20;       }

&#x20;       result = \[]

&#x20;       mixing = \[]

&#x20;       if not digits:

&#x20;           return \[]

&#x20;       def backtrack(index):

&#x20;           if index == len(digits):

&#x20;               result.append("".join(mixing))

&#x20;               return

&#x20;           current\_digit = int(digits\[index])

&#x20;           letters = combinations\[current\_digit]

&#x20;           for letter in letters:

&#x20;               mixing.append(letter)

&#x20;               backtrack(index + 1)

&#x20;               mixing.pop()

&#x20;       backtrack(0)

&#x20;       return result

solution = Solution()

print(solution.letterCombinations("69"))

Introducción

Qué son los grafos y cómo modelan el mundo

Qué es un árbol en estructuras de datos

Qué es la recursión en programación

Grafos en el mundo real que ya conoces

Representación de Grafos: Matriz y Lista de Adyacencia

DFS

Cómo recorre nodos el algoritmo DFS

Implementación de DFS recursivo para búsqueda en árboles

Búsqueda en Profundidad (DFS) para Grafos: Enfoque Iterativo y Recursivo

Inorder, Preorder y Postorder en árboles

Suma de caminos raíz a hoja en árboles

Suma de caminos raíz a hoja con DFS

Playground: Sum Root to Leaf Numbers

Implementación de Algoritmo DFS en Árboles Binarios con Golang

Número de islas con DFS en matrices

Problema de islas resuelto con DFS

Playground: Number of Islands

Número de islas con DFS recursivo en Python

Ejercicios Prácticos de Búsqueda en Profundidad (DFS)

Algoritmos de Búsqueda en Profundidad (DFS) en Problemas Comunes

BFS

Cómo BFS recorre grafos por niveles

Implementación de BFS con colas en Python

Mínimos movimientos del caballo en ajedrez

Minimum Knight's Move con BFS

Playground: Minimum Knights Moves

Resolución de Problemas de Caballos de Ajedrez con BFS en Python

Propagación BFS en Rotting Oranges

Resolución de Rotting Oranges usando BFS

Playground: Rotting Oranges

Implementación de BFS para naranjas podridas

Puente más corto entre islas con BFS

Shortest Bridge: combina DFS y BFS

Playground: Shortest Bridge Between Islands

Shortest Bridge con DFS y BFS en Python

Búsqueda en anchura: Ejercicios prácticos y aplicaciones

Ejercicios avanzados de búsqueda en anchura (BFS) en programación

Backtrack

Backtracking para encontrar soluciones válidas

Combinaciones de letras en teclado telefónico

Combinaciones de teclado con backtracking