Longest Common Prefix

Q: Qual è la complessità temporale del prefisso comune più lungo?

Entrambe le scansioni richiedono un tempo O(S) , dove S è il numero totale di lettere in tutte le parole, e necessitano solo di O(1) memoria aggiuntiva oltre alla risposta. Anche la scansione per colonne è limitata da n × (L+1) , dove L è la lunghezza della risposta, quindi si interrompe prima se le parole non corrispondono vicino all'inizio.

Q: Che cosa dovrebbe restituire Longest Common Prefix quando non c’è alcun prefisso comune?

Restituisce la stringa vuota "" . Succede non appena due parole iniziano con lettere diverse, come in stack , queue e heap .

Q: Quale è meglio, la scansione orizzontale o quella verticale?

Entrambi hanno lo stesso caso peggiore, O(S) . La scansione verticale, colonna per colonna, è la scelta più sicura: si ferma alla prima colonna in cui una qualsiasi parola non coincide, mentre la scansione orizzontale può confrontare un prefisso lungo con molte parole prima che una parola successiva lo interrompa.

FacileArray e stringhe

+10

Ricevi un array di parole strs. Restituisci la stringa più lunga con cui inizia ogni parola. Se le parole non iniziano tutte con la stessa lettera, restituisci la stringa vuota "". Una parola è considerata prefisso di sé stessa, quindi una singola parola è la risposta.

Funzione

longestCommonPrefix(strs: string-array) → string

strsstring-array: le parole da confrontare
Restituiscestring: il prefisso più lungo condiviso da tutte le parole, oppure una stringa vuota

Vincoli

1 ≤ strs.length ≤ 200
1 ≤ strs[i].length ≤ 200
Ogni parola contiene solo lettere minuscole inglesi.

Esempi

Input: strs = ["interview", "internet", "interval", "internal"]
Output: "inter"
Spiegazione: Tutte e quattro le parole iniziano con inter. Alla posizione successiva interview e interval hanno una v, internet e internal una n, quindi il prefisso si ferma lì.

Input: strs = ["stack", "queue", "heap"]
Output: ""
Spiegazione: Le parole iniziano con s, q e h. Differiscono già nella prima lettera, quindi non condividono alcun prefisso e la risposta è vuota.

Input: strs = ["prefix", "pre", "prepare"]
Output: "pre"
Spiegazione: pre è la parola più corta e le altre due iniziano con essa, quindi è l’intera risposta. Un prefisso comune non può mai essere più lungo della parola più corta.

+19 test nascosti all’invio

Per approfondire

Supponiamo che l'elenco rimanga fisso e che tu riceva molte parole da usare come query. Come troveresti, per ciascuna query, il prefisso più lungo che condivide con almeno una parola nell'elenco, senza scansionare di nuovo l'elenco ogni volta?

Suggerimenti

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

0 di 3 aperti

Soluzione

Una lettera fa parte della risposta solo se ogni parola ha la stessa lettera nella stessa posizione, e la risposta termina alla prima posizione in cui una parola non coincide o finisce. Entrambi gli approcci qui sotto leggono le parole lettera per lettera; differiscono nell'ordine in cui le leggono. La scansione per colonna si ferma al primo disaccordo, quindi non legge mai oltre la risposta più una colonna.

Riduci il prefisso parola per parola

Intuizione

Inizia supponendo che l’intera prima parola sia la risposta. Poi confrontala con la seconda parola, lettera per lettera, e riducila alla parte che hanno in comune. Confronta ciò che rimane con la terza parola, e così via. Dopo l’ultima parola, ciò che rimane è comune a tutte.

È corretto perché il prefisso comune di molte parole è il prefisso comune delle prime due, poi di quel risultato e della terza parola, e così via: ogni passaggio può solo mantenerlo o accorciarlo. Per interview, internet, interval, internal, il candidato passa da interview a inter dopo la seconda parola e rimane tale.

Ogni lettera viene confrontata al massimo una volta, quindi il tempo è O(S), dove S è il numero totale di lettere. Conservi solo una lunghezza, non una copia. Il punto debole è l’ordine: con 200 parole di 200 lettere, in cui le prime 199 concordano e solo l’ultima differisce alla prima lettera, confronti tutte le 200 lettere con ciascuna delle prime 199 parole, per un totale di quasi 40,000 confronti, prima che l’ultima parola riduca il prefisso a niente.

Algoritmo

Imposta prefixLen sulla lunghezza di strs[0].
Per ogni altra parola, conta quante lettere iniziali ha in comune con strs[0], fino a prefixLen.
Imposta prefixLen su quel conteggio e interrompi in anticipo se raggiunge 0.
Restituisci le prime prefixLen lettere di strs[0].

def longestCommonPrefix(strs):
    first = strs[0]
    prefix_len = len(first)
    for word in strs[1:]:
        common = 0
        while common < prefix_len and common < len(word) and word[common] == first[common]:
            common += 1
        prefix_len = common
        if prefix_len == 0:
            break
    return first[:prefix_len]

Confronta colonna per colonna

Intuizione

Leggi le parole come una tabella, una colonna alla volta. La colonna 0 contiene la prima lettera di ogni parola, la colonna 1 la seconda, e così via. Prendi la lettera di strs[0] nella colonna corrente e verifica che tutte le altre parole abbiano la stessa lettera in quella posizione. La prima volta che una parola non corrisponde, o è troppo corta per avere quella colonna, la risposta è strs[0] fino a quella colonna.

La risposta è esattamente la sequenza di colonne in cui tutte le parole corrispondono, e questo ciclo percorre quelle colonne da sinistra e si ferma alla prima che interrompe la sequenza. Se nessuna colonna la interrompe, la risposta è strs[0]; in tal caso è la parola più corta o è a pari merito con essa.

Il ciclo legge al massimo una colonna oltre la risposta, quindi con n parole e una risposta di lunghezza L esegue al massimo n × (L+1) verifiche e non legge mai due volte la stessa lettera di una parola, quindi è anche O(S). Nel caso precedente, in cui 199 parole corrispondono e l'ultima parola differisce nella prima lettera, si ferma dopo la prima colonna: 199 confronti invece di quasi 40.000.

Algoritmo

Imposta first su strs[0].
Per ogni colonna col da 0 alla lunghezza di first meno uno, leggi first[col].
Per ogni altra parola, se non ha una lettera in corrispondenza di col o la sua lettera è diversa, restituisci le prime col lettere di first.
Se tutte le colonne corrispondono, restituisci first.

def longestCommonPrefix(strs):
    first = strs[0]
    for col in range(len(first)):
        for word in strs[1:]:
            if col == len(word) or word[col] != first[col]:
                return first[:col]
    return first

Trappole e casi limite

La risposta è breve e i bug si trovano alla fine.

Leggere oltre la fine di una parola più corta. In prefix, pre, prepare, la colonna 3 esiste in prefix ma non in pre; controlla la lunghezza prima di leggere la lettera.
Confrontare solo la prima e l’ultima parola nell’ordine dato. Questa scorciatoia richiede che le parole vengano prima ordinate: in abc, xbd, abd, la prima e l’ultima condividono ab, ma xbd interrompe la colonna 0 e la risposta è vuota.
Restituire null o un segnaposto quando non c’è nulla in comune. La risposta è la stringa vuota.
Dimenticare che una singola parola è il proprio prefisso: algorithm da sola restituisce algorithm.
Costruire la risposta aggiungendo una lettera alla volta a una stringa immutabile. Per una risposta di 200 lettere, sono 200 copie; mantieni una lunghezza e ricava un taglio iniziale dalla prima parola una sola volta, alla fine.

Domande frequenti4

Qual è la complessità temporale del prefisso comune più lungo?

Entrambe le scansioni richiedono un tempo O(S), dove S è il numero totale di lettere in tutte le parole, e necessitano solo di O(1) memoria aggiuntiva oltre alla risposta. Anche la scansione per colonne è limitata da n × (L+1), dove L è la lunghezza della risposta, quindi si interrompe prima se le parole non corrispondono vicino all'inizio.

Riesci a trovare il prefisso comune più lungo ordinando le parole?

Sì. In ordine alfabetico, ogni parola che si trova tra la prima e l’ultima inizia con ciò che queste due hanno in comune, quindi confrontare solo la prima e l’ultima parola dà la risposta. L’ordinamento confronta circa n log n coppie di parole, il che costa più di una singola scansione, ma il codice è breve.

Che cosa dovrebbe restituire Longest Common Prefix quando non c’è alcun prefisso comune?

Restituisce la stringa vuota "". Succede non appena due parole iniziano con lettere diverse, come in stack, queue e heap.

Quale è meglio, la scansione orizzontale o quella verticale?

Entrambi hanno lo stesso caso peggiore, O(S). La scansione verticale, colonna per colonna, è la scelta più sicura: si ferma alla prima colonna in cui una qualsiasi parola non coincide, mentre la scansione orizzontale può confrontare un prefisso lungo con molte parole prima che una parola successiva lo interrompa.

Python

def longestCommonPrefix(strs):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

strs = ["interview", "internet", "interval", "internal"]

Atteso

"inter"