Letter Combinations of a Phone Number

Q: Qual è la complessità temporale delle combinazioni di lettere di un numero di telefono?

È O(4^n · n) per n cifre: possono esserci 4^n stringhe, quando ogni cifra è 7 o 9, e per scrivere ciascuna servono n passaggi. Con tasti con solo tre lettere, è O(3^n · n) . Nessuna soluzione può fare meglio, perché questa è la dimensione dell’output. Il backtracking richiede O(n) spazio aggiuntivo oltre all’output.

MedioBacktracking

+10

Su una tastiera telefonica, ogni cifra da 2 a 9 corrisponde a qualche lettera: 2 è abc, 3 è def, 4 è ghi, 5 è jkl, 6 è mno, 7 è pqrs, 8 è tuv e 9 è wxyz.

Hai una stringa digits. Scegli una lettera per ogni cifra, mantenendo le cifre nello stesso ordine, e ottieni una stringa che i tasti possono digitare. Restituisci tutte le stringhe possibili, ordinate in ordine lessicografico (alfabetico). Per "23" ci sono nove stringhe, da "ad" a "cf".

Funzione

letterCombinations(digits: string) → string-array

digitsstring: le cifre premute, ciascuna da 2 a 9
Restituiscestring-array: ogni stringa che i tasti possono digitare, in ordine lessicografico

Vincoli

1 ≤ digits.length ≤ 4
Ogni carattere di digits è una cifra da 2 a 9.
La risposta contiene al massimo 4⁴ = 256 stringhe.

Esempi

Input: digits = "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
Spiegazione: 2 offre a, b, c e 3 offre d, e, f. Ogni prima lettera si abbina a ogni seconda lettera, quindi ci sono 3 × 3 = 9 stringhe, e elencarle facendo cambiare più lentamente la prima lettera le mantiene ordinate.

Input: digits = "94"
Output: ["wg", "wh", "wi", "xg", "xh", "xi", "yg", "yh", "yi", "zg", "zh", "zi"]
Spiegazione: 9 ha quattro lettere e 4 ne ha tre, quindi ci sono 4 × 3 = 12 stringhe. Tutte e tre le stringhe che iniziano con w vengono prima della prima che inizia con x.

+14 test nascosti all’invio

Per approfondire

Supponiamo che tu voglia solo le combinazioni che sono parole reali presenti in un dizionario. Come eviteresti di generare prima tutte le stringhe di 4^n?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Qui non si può saltare nulla: la risposta stessa contiene fino a 4^n stringhe, quindi ogni soluzione corretta richiede almeno altrettanto lavoro per scriverle. Ciò che il problema verifica è se sai generare sistematicamente un insieme di scelte, senza ometterne o ripeterne nessuna. Questo è il backtracking nella sua forma più semplice: un albero decisionale con un livello per ogni cifra, percorso in profondità, in cui ogni foglia è una risposta.

Costruisci le stringhe una cifra alla volta

Intuizione

Costruisci le risposte una cifra alla volta. Inizia con un elenco che contiene una stringa vuota. Per "23", la cifra 2 la trasforma in a, b, c. La cifra 3 poi espande ciascuna di queste tre aggiungendo d, e e f, ottenendo nove stringhe di lunghezza 2. Dopo l'ultima cifra, l'elenco contiene tutte le risposte.

L'ordine risulta già ordinato senza alcuno sforzo. Supponiamo che l'elenco sia ordinato prima di elaborare una cifra. Estendi i prefissi mantenendo lo stesso ordine e, per ogni prefisso, aggiungi le lettere del tasto da sinistra a destra. Una stringa con un prefisso precedente viene ancora prima, mentre due stringhe con lo stesso prefisso sono ordinate in base alla nuova lettera, secondo l'ordine alfabetico.

Il costo dipende dalla dimensione della risposta. Con n cifre, l'ultimo elenco contiene fino a 4^n stringhe di lunghezza n e tutti gli elenchi precedenti insieme contengono al massimo la metà di stringhe, tutte più corte. Lo svantaggio è la memoria: mentre costruisci un livello, viene mantenuto anche tutto il livello precedente, compresi tutti i prefissi brevi che scarterai.

Algoritmo

Inizia con combos = [""], un prefisso vuoto.
Per ogni cifra, crea una nuova lista: per ogni prefisso in combos e ogni lettera sul tasto di quella cifra, aggiungi prefix + letter.
Sostituisci combos con la nuova lista.
Dopo l’ultima cifra, restituisci 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

Backtracking sull'albero decisionale

Intuizione

Immagina la risposta come un albero decisionale. La radice è una stringa vuota. Per "23" ha tre figli, a, b e c, uno per ogni lettera di 2. Ognuno di essi ha tre figli a sua volta, uno per ogni lettera di 3. L’albero ha un livello per ogni cifra e le nove foglie, da ad a cf, sono esattamente le risposte.

Il backtracking attraversa quell’albero in profondità usando un unico buffer, path. Al livello i scegli una lettera di digits[i] aggiungendola, esplori tutto ciò che si trova sotto di essa ricorrendo su i+1 e annulli la scelta rimuovendo la lettera. È l’annullamento che permette a un unico buffer di servire l’intero albero: dopo aver salvato ad, ae e af, rimuovere l’ultimo carattere riporta path a a, poi alla stringa vuota, pronto per b. Quando i è uguale alla lunghezza di digits, il buffer contiene una risposta completa e ne salvi una copia.

Provare le lettere da sinistra a destra a ogni livello visita le foglie in ordine alfabetico, quindi non serve ordinare l’output. In questo problema ogni ramo termina con una risposta, quindi non c’è nulla da potare; l’albero è profondo solo 4 livelli e ha al massimo 256 foglie. Il lavoro è comunque O(4^n · n) per scrivere le risposte, ma la memoria aggiuntiva è il buffer e lo stack delle chiamate, O(n), invece di un intero livello di prefissi. Lo stesso ciclo scegli, esplora, annulla risolve i sottoinsiemi, le permutazioni, la somma delle combinazioni e la ricerca di parole.

Algoritmo

Mantieni un path vuoto e un result vuoto.
Definisci backtrack(i): se i è uguale alla lunghezza di digits, salva una copia di path e restituisci.
Altrimenti, per ogni lettera sul tasto di digits[i], in ordine: aggiungila a path, chiama backtrack(i+1), poi rimuovila.
Chiama backtrack(0) e restituisci 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

Trappole e casi limite

La ricerca in sé è breve, quindi la maggior parte dei bug deriva dal tastierino o dal buffer condiviso.

Supporre che ogni tasto abbia tre lettere. 7 è pqrs e 9 è wxyz, quindi prendere tre lettere dall’indice (d-2)*3 dell’alfabeto esclude la s del 7 e fa iniziare l’8 con s invece che con t. Scrivi il tastierino in una tabella.
Dimenticare di annullare la modifica. Senza rimuovere la lettera dopo la chiamata ricorsiva, path continua a crescere e la seconda risposta per "23" risulta ade invece di ae.
Salvare il buffer invece di una copia. In Python, result.append(path) salva la stessa lista nove volte e alla fine è vuota. Quando la salvi, uniscila in una nuova stringa.
Perdere l’ordine. Provare le lettere di un tasto da destra a sinistra, o costruire le stringhe partendo da uno stack nella versione iterativa, produce le risposte in un ordine diverso da quello ordinato richiesto dal problema.
Leggere una stringa di cifre come un numero. In linguaggi tipizzati in modo permissivo come PHP e R, "23" potrebbe arrivarti come numero 23. Convertilo in testo prima di indicizzarne i caratteri.

Domande frequenti4

Qual è la complessità temporale delle combinazioni di lettere di un numero di telefono?

È O(4^n · n) per n cifre: possono esserci 4^n stringhe, quando ogni cifra è 7 o 9, e per scrivere ciascuna servono n passaggi. Con tasti con solo tre lettere, è O(3^n · n). Nessuna soluzione può fare meglio, perché questa è la dimensione dell’output. Il backtracking richiede O(n) spazio aggiuntivo oltre all’output.

Riesci a risolvere le combinazioni di lettere senza ricorsione?

Sì. Costruisci le risposte livello per livello: parti da una stringa vuota e, per ogni cifra, estendi ogni stringa che hai con ogni lettera di quel tasto. Esegue la stessa quantità di lavoro e percorre lo stesso albero in ampiezza invece che in profondità. Mantiene in memoria un intero livello di prefissi, mentre la ricorsione ha bisogno solo di uno stack profondo quanto il numero di cifre.

Perché il backtracking restituisce le combinazioni in ordine ordinato?

Tutte le risposte hanno la stessa lunghezza e una visita in profondità completa ogni stringa che inizia con a prima di scegliere b al primo livello. Lo stesso vale a ogni livello, purché le lettere di ciascuna chiave vengano provate da sinistra a destra. Questo è esattamente l’ordine lessicografico, quindi non è necessario ordinare.

Che dire delle cifre 0 e 1?

Su una tastiera telefonica, 0 e 1 non corrispondono ad alcuna lettera e questa versione del problema usa solo le cifre da 2 a 9. Se potessero comparire, dovresti decidere se saltare una cifra del genere o se rende vuota la risposta, dato che non offre alcuna lettera da scegliere. In un colloquio, chiedi quale comportamento si desidera prima di scrivere il codice.

Python

def letterCombinations(digits):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

digits = "23"

Atteso

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