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?

Es O(4^n · n) para n dígitos: puede haber 4^n cadenas cuando cada dígito es 7 o 9, y se necesitan n pasos para escribir cada una. Con teclas de solo tres letras, es O(3^n · n) . Ninguna solución puede hacerlo mejor, porque ese es el tamaño de la salida. El retroceso necesita O(n) espacio adicional, aparte de la salida.

MedioBacktracking

+10

En el teclado de un teléfono, cada dígito del 2 al 9 tiene asignadas 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.

Se te da una cadena digits. Elige una letra para cada dígito, manteniendo los dígitos en su orden, y obtendrás una cadena que se puede escribir con las teclas. Devuelve todas esas cadenas, ordenadas lexicográficamente (como en un diccionario). Para "23" son nueve cadenas, desde "ad" hasta "cf".

Función

letterCombinations(digits: string) → string-array

digitsstring: los dígitos pulsados, cada uno del 2 al 9
Devuelvestring-array: cada cadena que las teclas pueden escribir, 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, así que hay 3 × 3 = 9 cadenas, y enumerarlas haciendo que la primera letra cambie más lentamente las mantiene ordenadas.

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 van antes de la primera que empieza con x.

+14 pruebas ocultas al enviar

Para ir más allá

Supón que solo quieres las combinaciones que son palabras reales de un diccionario. ¿Cómo evitarías construir 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

No se puede omitir nada aquí: la respuesta contiene hasta 4^n cadenas, así que toda solución correcta dedica al menos ese trabajo a escribirlas. Lo que evalúa el problema es si puedes generar un conjunto de opciones de forma sistemática, sin omitir ni repetir ninguna. Eso es retroceso en su forma más sencilla: un árbol de decisiones con un nivel por dígito, recorrido en profundidad, donde cada hoja es una respuesta.

Construye las cadenas dígito a dígito

Intuición

Construye las respuestas de un dígito a la vez. Empieza con una lista que contenga una cadena vacía. Para "23", el dígito 2 la convierte en a, b, c. Después, el dígito 3 amplía cada una de esas tres con d, e y f, lo que da nueve cadenas de longitud 2. Después del último dígito, la lista contiene todas las respuestas.

El orden queda ordenado automáticamente. Supón que la lista está ordenada antes de procesar un dígito. Amplías los prefijos en ese mismo orden y cada prefijo con las letras de la tecla, de izquierda a derecha. Una cadena con un prefijo anterior sigue apareciendo primero, y dos cadenas con el mismo prefijo quedan ordenadas por la nueva letra, que es el orden alfabético.

El costo es el tamaño de la respuesta. Con n dígitos, la última lista tiene hasta 4^n cadenas de longitud n, y todas las listas anteriores juntas contienen como máximo la mitad de esa cantidad de cadenas, todas ellas más cortas. El inconveniente es la memoria: mientras construyes un nivel, también se conserva todo el nivel anterior, incluidos todos los prefijos cortos que descartarás.

Algoritmo

Empieza con combos = [""], un prefijo vacío.
Para cada dígito, crea una lista nueva: para cada prefijo de 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

Piensa en la respuesta como un árbol de decisiones. La raíz es una cadena vacía. Para "23" tiene tres hijos, a, b y c, uno por cada letra del 2. Cada uno de ellos tiene tres hijos propios, uno por cada letra del 3. El árbol tiene un nivel por dígito, y las nueve hojas, de ad a cf, son exactamente las respuestas.

El retroceso recorre ese árbol en profundidad con un único búfer, path. En el nivel i, eliges una letra de digits[i] agregándola, exploras todo lo que hay debajo recursando con i+1 y deshaces la elección quitando la letra. Deshacer la elección es lo que permite que un mismo búfer sirva para todo el árbol: después de guardar ad, ae y af, quitar la última letra devuelve path a a y luego a la cadena vacía, lista para b. Cuando i es igual a la longitud de digits, el búfer contiene una respuesta completa y guardas una copia.

Probar las letras de izquierda a derecha en cada nivel visita las hojas en orden alfabético, así que no hace falta ordenar la salida. En este problema, cada rama termina en una respuesta, por lo que no hay nada que podar; el árbol tiene solo 4 niveles de profundidad y como máximo 256 hojas. El trabajo sigue siendo O(4^n · n) para escribir las respuestas, pero la memoria adicional es el búfer y la pila de llamadas, O(n), en vez de un nivel entero de prefijos. El mismo ciclo de elegir, explorar y deshacer resuelve problemas de subconjuntos, permutaciones, suma de combinaciones y búsqueda de palabras.

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

La búsqueda en sí es breve, así que la mayoría de los errores provienen del teclado o del búfer compartido.

Suponer que cada tecla tiene tres letras. 7 es pqrs y 9 es wxyz, así que tomar tres letras desde el índice (d-2)*3 del alfabeto omite la s del 7 y hace que el 8 empiece con s en lugar de t. Escribe el teclado en forma de tabla.
Olvidar deshacer el cambio. Sin quitar la letra después de la llamada recursiva, path sigue creciendo, y la segunda respuesta para "23" resulta ser ade en lugar de ae.
Guardar el búfer en lugar de una copia. En Python, result.append(path) almacena la misma lista nueve veces, y al final queda vacía. Al guardarla, conviértela en una cadena nueva.
Perder el orden. Probar las letras de una tecla de derecha a izquierda, o hacer crecer las cadenas desde una pila en la versión iterativa, da las respuestas en un orden distinto del ordenado que pide el problema.
Leer una cadena de dígitos como un número. En lenguajes con tipado débil, como PHP y R, puede que recibas "23" como el número 23. Conviértelo en texto antes de indexar sus caracteres.

Preguntas frecuentes4

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

Es O(4^n · n) para n dígitos: puede haber 4^n cadenas cuando cada dígito es 7 o 9, y se necesitan n pasos para escribir cada una. Con teclas de solo tres letras, es O(3^n · n). Ninguna solución puede hacerlo mejor, porque ese es el tamaño de la salida. El retroceso necesita O(n) espacio adicional, aparte de la salida.

¿Puedes resolver Combinaciones de letras sin recursión?

Sí. Construye las respuestas nivel por nivel: empieza con una cadena vacía y, por cada dígito, amplía cada cadena que tengas con cada letra de esa tecla. Realiza la misma cantidad de trabajo y recorre el mismo árbol en anchura en lugar de en profundidad. Mantiene en memoria todo un nivel de prefijos, mientras que la recursión solo necesita una pila cuya profundidad sea igual al número de dígitos.

¿Por qué la retropropagación devuelve las combinaciones ordenadas?

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

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

En un teclado numérico de teléfono, 0 y 1 no tienen letras, y esta versión del problema solo usa los números 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, ya que no ofrece ninguna letra para elegir. En una entrevista, pregunta cuál de las dos opciones se desea antes de programarlo.

Python

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

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

digits = "23"

Esperado

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