Combinaciones de Letras en Números Telefónicos

Clase 37 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles

Resumen

¿Qué son las combinaciones de letras de un número de teléfono?

Las combinaciones de letras de un número de teléfono son un problema clásico de programación que se centra en generar todas las posibles combinaciones de letras que un número telefónico podría representar en un teclado tradicional de teléfono. Este desafío implica tomar una cadena de dígitos del 2 al 9 y devolver todas las combinaciones posibles en cualquier orden según las letras asignadas a cada botón.

¿Cómo funciona la asignación de letras a números?

En los antiguos teléfonos de botones, cada número del 2 al 9 tenía asociadas una serie de letras específicas. La asignación típica es:

2: A, B, C
3: D, E, F
4: G, H, I
5: J, K, L
6: M, N, O
7: P, Q, R, S
8: T, U, V
9: W, X, Y, Z

Es importante recordar que los números 1 y 0 no tienen letras asociadas a ellos. Estos detalles son esenciales para abordar el problema correctamente.

¿Cómo se puede resolver el problema de combinaciones?

Resolviendo este problema, primero se debe visualizar como un reto de generación de combinaciones de letras a partir de una cadena de dígitos. La idea es entender que cada dígito puede representar varias letras, y se busca formar todas las posibles palabras o secuencias de letras que se pueden construir con estos.

Ejemplo de entrada y salida

Supongamos que el número de entrada es "23". Las combinaciones posibles de letras se obtendrían al considerar todas las combinaciones individuales de las letras del 2 (A, B, C) con las letras del 3 (D, E, F):

Este es un ejercicio excelente para pensar en cómo se podrían usar estructuras de datos y algoritmos como recursividad o programación dinámica para generar estas combinaciones de manera eficiente.

¿Qué pasos seguir para intentar resolver el problema?

Para abordar este problema:

Entender el mapeo: Asegúrate de comprender bien la asignación de letras a números.
Generar combinaciones: Considera usar una función recursiva que construya las combinaciones letra por letra, agregando una letra de cada vez dependiendo del dígito.
Considerar casos especiales: Presta atención a situaciones donde la cadena de entrada pueda contener un 1 o 0, que se deben ignorar.
Optimización: Busca formas de optimizar tu algoritmo para manejar cadenas más largas de manera eficiente.

Prueba por ti mismo

Antes de lanzarte a programar, intenta resolver el problema en papel o usando un pseudocódigo. Analiza las diferentes combinaciones y busca patrones que puedan ayudarte a construir una solución que no solo funcione, sino que sea entendible y optimizada. ¡Buena suerte!

Andres Silva Vega

student•

Dejo mi forma de resolverlo en javascript usando recursión. Me pareció que se resuelve con la implementación de un algoritmo DFS

class TeclasTelefono {
    constructor(numero_tel){
        this.numero_tel = numero_tel.replace( /[^2-9]+/g , "");
        console.log(`Solo se permiten numeros de 2 al 9. La entreda queda ${this.numero_tel}`);
        for(let i = 2 ; i <= 9 ; i++){
            this.numero_tel = this.numero_tel.replace(i+"",(i-2) + "");
        }
        this.teclado = [
            ["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"],
        ];
    }
    combinacion_sin_backtraking(){
        let numero_array = [];
        for(let  i = 0; i < this.numero_tel.length; i++){
            numero_array.push(this.teclado[parseInt(this.numero_tel[i])]);
        }
        if(numero_array.length > 0){
            return this.combinar(numero_array);
        }
        return [];
    }
    combinar (maleta){
        let anterior_array = [];
        let nuevo_array = [];
        let current = maleta.shift();
        if(maleta.length > 0){
            anterior_array = this.combinar(maleta);
        }
        if(current.length > 0){
            for(let i = 0; i < current.length; i++){
                if(anterior_array.length > 0){
                    anterior_array.forEach(ele => {
                        nuevo_array.push(current[i] + ele);
                    });
                } else {
                    return current;
                }
            }
        }
        return nuevo_array;
    }
}

Andres Silva Vega

student•

Dejo mi forma de resolverlo en javascript usando recursión. Me pareció que se resuelve con la implementación de un algoritmo BFS

class TeclasTelefono {
    constructor(numero_tel){
        this.numero_tel = numero_tel.replace( /[^2-9]+/g , "");
        console.log(`Solo se permiten numeros de 2 al 9. La entreda queda ${this.numero_tel}`);
        for(let i = 2 ; i <= 9 ; i++){
            this.numero_tel = this.numero_tel.replace(i+"",(i-2) + "");
        }
        this.teclado = [
            ["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"],
        ];
    }
    combinacion_sin_backtraking(){
        let numero_array = [];
        for(let  i = 0; i < this.numero_tel.length; i++){
            numero_array.push(this.teclado[parseInt(this.numero_tel[i])]);
        }
        if(numero_array.length > 0){
            return this.combinar(numero_array);
        }
        return [];
    }
    combinar (maleta){
        let anterior_array = [];
        let nuevo_array = [];
        let current = maleta.shift();
        if(maleta.length > 0){
            anterior_array = this.combinar(maleta);
        }
        if(current.length > 0){
            for(let i = 0; i < current.length; i++){
                if(anterior_array.length > 0){
                    anterior_array.forEach(ele => {
                        nuevo_array.push(current[i] + ele);
                    });
                } else {
                    return current;
                }
            }
        }
        return nuevo_array;
    }
}