Letter Combinations of a Phone Number

Q: ¿Cuál es la complejidad temporal de las combinaciones de letras de un número de teléfono?

O(4^n · n) para n dígitos: puede haber 4^n cadenas cuando cada dígito es 7 o 9, y escribir cada una requiere n pasos. Ese es el tamaño de la salida, así que ninguna solución puede hacerlo mejor. El retroceso requiere O(n) espacio adicional, aparte de la salida.

MedioBacktracking

+10

En un teclado de teléfono, cada dígito del 2 al 9 tiene algunas letras: 2 es abc, 3 es def, 4 es ghi, 5 es jkl, 6 es mno, 7 es pqrs, 8 es tuv y 9 es wxyz.

Recibes una cadena digits. Elige una letra para cada dígito, manteniendo los dígitos en su orden, y obtienes una cadena que se puede escribir con las teclas. Devuelve todas esas cadenas, ordenadas en orden lexicográfico (de diccionario).

Función

letterCombinations(digits: string) → string-array

digitsstring: los dígitos pulsados, cada uno del 2 al 9
Devuelvestring-array: cada cadena que pueden escribir las teclas, en orden lexicográfico

Restricciones

1 ≤ digits.length ≤ 4
Cada carácter de digits es un dígito del 2 al 9.
La respuesta contiene como máximo 4⁴ = 256 cadenas.

Ejemplos

Entrada: digits = "23"
Salida: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
Explicación: 2 ofrece a, b, c y 3 ofrece d, e, f. Cada primera letra se empareja con cada segunda letra: 3 × 3 = 9 cadenas, ordenadas de modo que la primera letra cambie más lentamente.

Entrada: digits = "94"
Salida: ["wg", "wh", "wi", "xg", "xh", "xi", "yg", "yh", "yi", "zg", "zh", "zi"]
Explicación: 9 tiene cuatro letras y 4 tiene tres, así que hay 4 × 3 = 12 cadenas. Las tres cadenas que empiezan con w vienen antes de la primera que empieza con x.

Para ir más allá

Supongamos que solo quieres las combinaciones que son palabras reales de un diccionario. ¿Cómo evitarías generar primero todas las cadenas de 4^n?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

La respuesta contiene hasta 4^n cadenas, así que cada solución requiere al menos esa cantidad de trabajo para escribirlas. Lo importante es producir cada opción una vez, sin omitir ni repetir ninguna. Eso es retroceder por un árbol de decisiones con un nivel por cada dígito, donde cada hoja es una respuesta.

Construye las cadenas de una cifra a la vez

Intuición

Empieza con una lista que contenga una cadena vacía y amplíala un dígito a la vez. Para "23", el dígito 2 la convierte en a, b, c, y el 3 amplía cada una con d, e y f, lo que da nueve cadenas.

El orden se mantiene ordenado. Si la lista está ordenada antes de procesar un dígito, amplías los prefijos en ese orden, y cada prefijo con las letras de su tecla de izquierda a derecha: un prefijo anterior sigue apareciendo primero, y los prefijos iguales se ordenan por la nueva letra.

El trabajo es proporcional al tamaño de la respuesta, pero mientras construyes un nivel, todo el nivel anterior también permanece en la memoria.

Algoritmo

Empieza con combos = [""], un prefijo vacío.
Para cada dígito, crea una lista nueva: por cada prefijo en combos y cada letra de la tecla de ese dígito, añade prefix + letter.
Reemplaza combos por la lista nueva.
Después del último dígito, devuelve combos.

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letterCombinations(digits):
    combos = [""]  # every prefix built so far; one empty prefix to start
    for digit in digits:
        # Each old prefix grows by each letter of this digit, in order.
        combos = [prefix + letter for prefix in combos for letter in KEYPAD[digit]]
    return combos

Retroceso en el árbol de decisiones

Intuición

Las respuestas son las hojas de un árbol de decisión. La raíz es la cadena vacía, y cada nivel añade una letra del siguiente dígito: para "23", la raíz tiene como hijos a, b, c, cada uno con hijos para d, e, f.

Recórrelo en profundidad con un solo búfer, path. En el nivel i, elige una letra de digits[i] añadiéndola, explora recursivamente con i+1 y deshaz el cambio eliminándola. Deshacer el cambio permite que un solo búfer sirva para todo el árbol: después de ad, ae y af, quitar el último carácter devuelve path a a, luego a la cadena vacía, listo para b. Cuando i llega al final de digits, guarda una copia.

El tiempo sigue siendo O(4^n · n), pero la memoria adicional consiste en el búfer y la pila de llamadas, O(n).

Algoritmo

Mantén un path vacío y un result vacío.
Define backtrack(i): si i es igual a la longitud de digits, guarda una copia de path y retorna.
De lo contrario, para cada letra de la tecla de digits[i], en orden: añádela a path, llama a backtrack(i+1) y después elimínala.
Llama a backtrack(0) y retorna result.

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letterCombinations(digits):
    result = []
    path = []  # the letters chosen so far, one per digit

    def backtrack(i):
        if i == len(digits):
            # Every digit has a letter: this leaf is one finished string.
            result.append("".join(path))
            return
        for letter in KEYPAD[digits[i]]:
            path.append(letter)   # choose
            backtrack(i + 1)      # explore the digits after this one
            path.pop()            # undo, so the next letter can take its place

    backtrack(0)
    return result

Errores comunes y casos límite

Suponer que cada tecla tiene tres letras. Tomar tres letras del alfabeto a partir del índice (d-2)*3 omite la s del 7 y hace que el 8 empiece en s. Escribe el teclado en forma de tabla.
Olvidar deshacer. path sigue creciendo y la segunda respuesta para "23" resulta ser ade en lugar de ae.
Guardar el búfer en vez de una copia. En Python, result.append(path) almacena la misma lista nueve veces y, al final, está vacía.
Probar las letras de una tecla de derecha a izquierda o construir cadenas a partir de una pila en la versión iterativa. Cualquiera de las dos cosas rompe el orden ordenado.
En PHP y R, "23" puede llegar como el número 23. Conviértelo en texto antes de indexar sus caracteres.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de las combinaciones de letras de un número de teléfono?

O(4^n · n) para n dígitos: puede haber 4^n cadenas cuando cada dígito es 7 o 9, y escribir cada una requiere n pasos. Ese es el tamaño de la salida, así que ninguna solución puede hacerlo mejor. El retroceso requiere O(n) espacio adicional, aparte de la salida.

¿Por qué la vuelta atrás devuelve las combinaciones en orden ordenado?

Todas las respuestas tienen la misma longitud, y un recorrido en profundidad termina cada cadena que empieza con a antes de elegir b. Lo mismo ocurre en cada nivel, siempre que las letras de cada clave se prueben de izquierda a derecha. Ese es el orden alfabético, así que no hace falta ordenar.

¿Qué pasa con los dígitos 0 y 1?

En un teclado telefónico, 0 y 1 no tienen letras, y esta versión solo usa del 2 al 9. Si pudieran aparecer, tendrías que decidir si se omite ese dígito o si hace que la respuesta quede vacía. En una entrevista, pregunta cuál de las dos opciones se prefiere.

def letterCombinations(digits):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

digits = "23"

Salida Esperada

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]