Resolver Letter Combinations of a Phone Number consiste en recibir un string de dígitos y devolver todas las combinaciones de letras que se pueden formar con el teclado de un teléfono. Es un ejercicio clásico para entrenar backtracking, DFS y el uso de hash tables en entrevistas técnicas.

La idea central es simple: cada número del 2 al 9 mapea a un grupo de letras, y tú debes generar todas las palabras posibles respetando el orden de los dígitos de entrada. Si te entregan "23", las salidas válidas incluyen ad, ae, af, bd, be, bf, cd, ce, cf.

Cómo se modela el teclado del teléfono en código

Antes de pensar en recursión, necesitas una estructura que traduzca cada dígito a sus letras. Aquí entra el hash table.

En un teléfono estándar, los números 1 y 0 no tienen letras asignadas, mientras que del 2 al 9 cada tecla agrupa entre 3 y 4 letras. Modelar esto con un diccionario te da acceso en tiempo constante a las letras de cualquier dígito [1:48].

¿Por qué usar un hash table aquí? Porque buscar las letras de un dígito se vuelve O(1). En lugar de recorrer estructuras grandes, accedes directo al grupo correspondiente y lo iteras, que al ser de tamaño fijo (máximo 4 letras) también cuenta como O(1).

La tabla queda así:

• 2 -> [a, b, c].
• 3 -> [d, e, f].
• Y así sucesivamente hasta 9 -> [w, x, y, z].

Con esto resuelto, ya tienes el cimiento para construir la recursión.

Por qué backtracking y DFS son la mejor estrategia

Cuando un problema te pide todas las combinaciones posibles respetando un orden, backtracking casi siempre aparece como respuesta natural.

La intuición es esta: empiezas en el primer dígito, eliges una letra, profundizas al siguiente dígito, eliges otra letra, y sigues hasta agotar la cadena. Cuando llegas al final, guardas la combinación. Luego retrocedes (de ahí el back) y pruebas la siguiente letra disponible. Ese descenso vertical hasta el fondo antes de explorar lateralmente es justamente Depth First Search [4:10].

¿Qué diferencia hay entre backtracking y DFS aquí? DFS es la forma de recorrer (ir lo más profundo posible primero); backtracking es la técnica de construir y deshacer soluciones parciales. En este problema se usan juntos.

La clave para que sea eficiente es no repetir trabajo. En lugar de recorrer mil veces el dígito 2 por cada combinación, iteras una sola vez por nodo y vas agregando la letra actual a las soluciones parciales acumuladas.

Cómo construir las combinaciones de forma recursiva

La función recursiva recibe la posición actual del dígito y la combinación que llevas construida hasta ese momento.

En cada llamada haces tres cosas:

1. Si la combinación parcial ya tiene la longitud del input, la guardas en la lista de resultados.
2. Si no, tomas el dígito actual, buscas sus letras en el hash table y recorres ese grupo.
3. Por cada letra, llamas recursivamente con la posición siguiente y la combinación extendida.

De esta forma, cuando llegas al dígito 2 generas a, b, c como soluciones parciales. Al avanzar al 3, a cada una le agregas d, e, f. El resultado son las nueve combinaciones esperadas, sin recorridos redundantes [3:30].

Cómo manejar duplicados si aparecen

En un teléfono real no hay letras repetidas entre teclas, pero imagina que sí. Si el 5 y el 6 compartieran la letra a, podrías generar combinaciones idénticas dos veces.

Para ese escenario, cambiar la lista de resultados por un hash set resuelve el problema. Un hash set verifica en O(1) si un elemento ya existe y descarta duplicados automáticamente [6:20]. No es necesario en la versión básica, pero es una buena defensa si el problema se complica.

Qué complejidad tiene esta solución

La complejidad temporal es O(4^n · n), donde n es la cantidad de dígitos del input. El 4 viene del peor caso de letras por tecla (como el 7 o el 9), y el factor n corresponde a construir cada string final.

La complejidad espacial sigue la misma lógica por la pila de recursión y el almacenamiento de resultados. Para inputs cortos como "23" es trivial; para inputs de 7 u 8 dígitos sigue siendo manejable.

¿Cuándo conviene backtracking en entrevistas? Siempre que escuches frases como "todas las combinaciones", "todas las permutaciones" o "todas las formas posibles". Es la señal de que necesitas exploración exhaustiva con poda.

Ahora que tienes el diseño claro (hash table + DFS recursivo + acumulación de soluciones parciales), el siguiente paso es implementarlo en tu lenguaje favorito y comparar tu versión con la de la próxima clase. ¿En qué lenguaje vas a programarla tú?