Letter Combinations of a Phone Number

Q: Qual è la complessità temporale di 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 scriverne ciascuna servono n passaggi. Questa è la dimensione dell'output, quindi nessuna soluzione può fare di meglio. 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.

Ti viene data una stringa digits. Scegli una lettera per ogni cifra, mantenendo le cifre nel loro ordine, e ottieni una stringa che i tasti possono digitare. Restituisci tutte le stringhe possibili, ordinate in ordine lessicografico (da dizionario).

Funzione

letterCombinations(digits: string) → string-array

digitsstring: le cifre premute, ciascuna da 2 a 9
Restituiscestring-array: tutte le stringhe 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: 3 × 3 = 9 stringhe, ordinate in modo che la prima lettera cambi più lentamente.

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.

Per approfondire

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

Suggerimenti

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

0 di 3 aperti

Soluzione

La risposta contiene fino a 4^n stringhe, quindi ogni soluzione richiede almeno altrettanto lavoro per scriverle. L'importante è produrre ogni scelta una volta, senza tralasciarne o ripeterne nessuna. Si tratta di backtracking su un albero decisionale con un livello per ogni cifra, in cui ogni foglia è una risposta.

Costruisci le stringhe una cifra alla volta

Intuizione

Inizia con una lista contenente una stringa vuota e ampliala di una cifra alla volta. Per "23", la cifra 2 la trasforma in a, b, c, e 3 amplia ciascuna di esse con d, e e f, ottenendo nove stringhe.

L’ordine rimane ordinato. Se la lista è ordinata prima di una cifra, amplii i prefissi in quell’ordine e ciascun prefisso con le lettere del suo tasto da sinistra a destra: un prefisso precedente rimane per primo e i prefissi uguali vengono ordinati in base alla nuova lettera.

Il lavoro richiesto dipende dalla dimensione della risposta, ma mentre costruisci un livello, anche l’intero livello precedente rimane in memoria.

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

Le risposte sono le foglie di un albero decisionale. La radice è la stringa vuota e ogni livello aggiunge una lettera della cifra successiva: per "23", la radice ha come figli a, b, c, ognuno dei quali ha come figli d, e, f.

Attraversalo in profondità usando un unico buffer, path. Al livello i, scegli una lettera di digits[i] aggiungendola, esplora ricorrendo su i+1 e annulla rimuovendola. L'annullamento permette a un unico buffer di servire l'intero albero: dopo ad, ae e af, rimuovere l'ultimo carattere riporta path a a, poi alla stringa vuota, pronto per b. Quando i raggiunge la fine di digits, salva una copia.

Il tempo resta O(4^n · n), ma la memoria aggiuntiva è quella del buffer e dello stack delle chiamate, O(n).

Algoritmo

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

Supporre che ogni tasto abbia tre lettere. Prendendo tre lettere dall’indice (d-2)*3 dell’alfabeto, si perde la s del 7 e l’8 inizia con s. Scrivi la tastiera in una tabella.
Dimenticare di annullare l’ultima modifica. 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) memorizza la stessa lista nove volte e, alla fine, è vuota.
Provare le lettere di un tasto da destra a sinistra o costruire stringhe partendo da uno stack nella versione iterativa. Entrambe le cose compromettono l’ordine alfabetico.
In PHP e R, "23" potrebbe arrivare come numero 23. Convertilo in testo prima di indicizzarne i caratteri.

Domande frequenti3

Qual è la complessità temporale di 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 scriverne ciascuna servono n passaggi. Questa è la dimensione dell'output, quindi nessuna soluzione può fare di meglio. Il backtracking richiede O(n) spazio aggiuntivo oltre all'output.

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. Lo stesso vale a ogni livello, purché le lettere di ogni chiave siano provate da sinistra a destra. Questo è l'ordine del dizionario, quindi non serve ordinare.

Che dire delle cifre 0 e 1?

Su una tastiera telefonica, 0 e 1 non corrispondono ad alcuna lettera e questa versione usa solo le cifre da 2 a 9. Se potessero comparire, dovresti decidere se saltare tale cifra o se questa rende vuota la risposta. In un colloquio, chiedi quale comportamento si desidera.

def letterCombinations(digits):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

digits = "23"

Output atteso

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