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, con memoria aggiuntiva O(1) oltre a quella necessaria per la risposta. Anche la scansione delle colonne è limitata da n × (L+1) per una risposta di lunghezza L , quindi si interrompe in anticipo quando le parole non corrispondono vicino all'inizio.

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

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

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

Entrambi hanno lo stesso caso peggiore, O(S) . La scansione verticale è la scelta più sicura: si ferma alla prima colonna in cui una parola qualsiasi non corrisponde, 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 dell'alfabeto inglese.

Esempi

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

Input: strs = ["stack", "queue", "heap"]
Output: ""
Spiegazione: Le parole iniziano con s, q e h. Sono diverse già dalla prima lettera, quindi la risposta è vuota.

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

Per approfondire

Supponiamo che l’elenco rimanga fisso e che arrivino molte parole di ricerca. Come troveresti il prefisso più lungo di ciascuna parola di ricerca condiviso con una parola dell’elenco, senza scansionare di nuovo l’elenco?

Suggerimenti

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

0 di 3 aperti

Soluzione

Una lettera appartiene alla risposta solo se tutte le parole ce l’hanno nella stessa posizione, e la risposta termina alla prima posizione in cui una parola non è d’accordo o finisce. Entrambi gli approcci leggono le parole lettera per lettera in un ordine diverso. La scansione per colonna si ferma al primo disaccordo.

Riduci il prefisso parola per parola

Intuizione

Supponi che la risposta sia l'intera prima parola. Riducila alla parte che ha in comune con la seconda parola, poi con la terza e così via. Il prefisso comune di molte parole è il prefisso comune delle prime due, poi di quello e della terza parola: a ogni passaggio può solo rimanere invariato o accorciarsi. Per esempio 1, il candidato passa da interview a inter dopo la seconda parola e rimane così.

Ogni lettera viene confrontata al massimo una volta, quindi il tempo è O(S) per S lettere in totale. Il punto debole è l'ordine: con 200 parole di 200 lettere in cui solo l'ultima parola differisce nella prima lettera, fai quasi 40.000 confronti prima che l'ultima parola riduca il prefisso a nulla.

Algoritmo

Imposta prefixLen alla lunghezza di strs[0].
Per ogni altra parola, conta quante lettere iniziali condivide con strs[0], fino a prefixLen.
Imposta prefixLen a quel conteggio e fermati prima 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. Prendi la lettera di strs[0] nella colonna corrente e verifica che ogni altra parola abbia 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 la percorre da sinistra e si ferma quando trova una differenza. Se non trova differenze, la risposta è strs[0].

Con n parole e una risposta di lunghezza L, il ciclo esegue al massimo n × (L+1) controlli, che corrispondono anche a O(S). Nel caso in cui solo l'ultima delle 200 parole differisca nella prima lettera, si ferma dopo 199 confronti.

Algoritmo

Sia first uguale a 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

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 senza ordinare. In abc, xbd, abd, le prime due 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.
Aggiungere una lettera alla volta a una stringa immutabile. Una risposta di 200 lettere richiede quindi 200 copie; mantieni una lunghezza e taglia la prima parola una sola volta.

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, con memoria aggiuntiva O(1) oltre a quella necessaria per la risposta. Anche la scansione delle colonne è limitata da n × (L+1) per una risposta di lunghezza L, quindi si interrompe in anticipo quando le parole non corrispondono vicino all'inizio.

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

Sì. In ordine alfabetico, ogni parola tra la prima e l’ultima inizia con ciò che queste due hanno in comune, quindi confrontare solo queste due 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?

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

Quale è migliore, la scansione orizzontale o quella verticale?

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

def longestCommonPrefix(strs):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

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

Output atteso

"inter"