Partition Labels
Hai una stringa s composta da lettere minuscole. Dividila nel maggior numero possibile di parti consecutive, in modo che ogni lettera compaia in una sola parte: se una lettera compare in una parte, tutte le sue occorrenze si trovano in quella parte. Restituisci le lunghezze delle parti da sinistra a destra.
Funzione
- sstring
- la stringa da tagliare, solo lettere minuscole
- Restituisceinteger-array
- la lunghezza di ciascuna parte, da sinistra a destra
Vincoli
1 ≤ s.length ≤ 5 × 104scontiene solo lettere inglesi minuscole.- Le parti mantengono il loro ordine e insieme compongono tutto
s, quindi le lunghezze sommate dannos.length.
Esempi
- Input
- s = "abacdcefe"
- Output
- [3, 3, 3]
- Spiegazione
- Le a si trovano alle posizioni 0 e 2, le c alle posizioni 3 e 5 e le e alle posizioni 6 e 8, quindi i tagli cadono dopo
abae dopocdc. Nessuna parte può essere tagliata di nuovo, perché ciascuna inizia e finisce con la stessa lettera.
- Input
- s = "codingisfun"
- Output
- [1, 1, 1, 8]
- Spiegazione
- Le lettere c, o e d compaiono una volta ciascuna, quindi ognuna forma una parte a sé. La i all’indice 3 ha una copia all’indice 6, e la n all’indice 4 ha una copia all’indice 10, la fine della stringa, quindi tutto ciò che va dall’indice 3 in poi è un’unica parte di 8 lettere.
- Input
- s = "zebraz"
- Output
- [6]
- Spiegazione
- La prima lettera, z, torna come ultima lettera, quindi l'intera stringa deve rimanere in un'unica parte.
+14 test nascosti all’invio
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
La prima parte deve contenere
s[0]. Quanto a destra deve arrivare, come minimo?Una parte che contiene una lettera deve raggiungere la sua ultima occorrenza, e ogni lettera che incontra lungo il percorso può spingerla più avanti. Registra prima l’ultima posizione di ogni lettera, così ogni ricerca costa
O(1).Leggi da sinistra a destra e tieni
end, la posizione più a destra tra le lettere della parte corrente. Quando la tua posizione è uguale aend, nessuna lettera della parte compare più avanti: taglia lì, registra la lunghezza e inizia una nuova parte.
Soluzione
Un taglio è consentito solo dove non compare alcuna lettera da entrambi i lati, e la risposta migliore prevede un taglio in ogni punto di questo tipo. Verificare ogni punto riesaminando la stringa richiede un tempo quadratico. Registra prima l'ultima posizione di ogni lettera: basta poi un'unica passata da sinistra a destra per trovare tutti i tagli, perché una parte deve estendersi fino all'ultima occorrenza di ogni lettera al suo interno.
Verifica ogni spazio vuoto
Corretto, ma non termina sui test più grandi
Intuizione
Ci sono n-1 spazi tra lettere adiacenti. È consentito tagliare in uno spazio solo quando nessuna lettera compare su entrambi i lati, perché una lettera divisa dal taglio si troverebbe in due parti. Effettuare tutti i tagli consentiti dà il maggior numero di parti. Prendi un pezzo compreso tra due tagli consentiti adiacenti: nessuna delle sue lettere compare a sinistra del taglio sinistro o a destra del taglio destro, quindi tutte le loro copie si trovano all'interno del pezzo, che è una parte valida. E qualsiasi risposta valida può tagliare solo negli spazi consentiti, quindi nessuna risposta può avere più parti.
Quindi controlla ogni spazio: raccogli le lettere alla sua sinistra e alla sua destra e taglia se i due insiemi non hanno elementi in comune. In abacdcefe lo spazio dopo aba ha a e b a sinistra e c, d, e e f a destra. Non c'è niente in comune, quindi tagli. Lo spazio dopo ab ha una a su entrambi i lati, quindi non tagli.
Ogni controllo legge l'intera stringa e ci sono n-1 spazi, quindi il lavoro richiede circa n² letture di lettere. Con 50.000 lettere sono 2.5 × 10^9 letture, troppo lento per i test più grandi.
Algoritmo
- Imposta
start = 0, dove inizia la parte corrente. - Per ogni punto di divisione
cutda 1 an-1(il punto subito prima dis[cut]), contrassegna le lettere dis[0..cut-1]e le lettere dis[cut..n-1]. - Se nessuna lettera è contrassegnata su entrambi i lati, aggiungi
cut-startalla risposta e impostastart = cut. - Dopo il ciclo, aggiungi l'ultima parte,
n-start.
def partitionLabels(s):
n = len(s)
sizes = []
start = 0 # where the current part begins
for cut in range(1, n): # the gap just before s[cut]
left = set(s[:cut])
right = set(s[cut:])
if not (left & right): # no letter on both sides: cut here
sizes.append(cut - start)
start = cut
sizes.append(n - start) # the last part has no gap after it
return sizesUnisci l'intervallo di ogni lettera
Intuizione
Pensa a ogni lettera come a un intervallo, dalla sua prima posizione all’ultima. Una parte che contiene una lettera deve coprire l’intero intervallo. Quindi due lettere i cui intervalli si sovrappongono devono appartenere alla stessa parte, e la sovrapposizione si propaga: se a si sovrappone a b e b si sovrappone a c, tutte e tre finiscono nella stessa parte.
Questo è il problema dell’unione degli intervalli. Registra la prima e l’ultima posizione di ogni lettera in un unico passaggio. Poi considera gli intervalli nell’ordine in cui iniziano e unisci quelli che si sovrappongono. Ogni blocco unito è una parte, e gli spazi tra i blocchi sono esattamente i punti in cui è consentito tagliare. Ottieni gli intervalli in ordine di inizio senza ordinare: percorri di nuovo la stringa e considera l’intervallo di una lettera quando ti trovi nella sua prima posizione.
In codingisfun, gli intervalli in ordine sono c [0, 0], o [1, 1], d [2, 2], i [3, 6], n [4, 10], g [5, 5], s [7, 7], f [8, 8] e u [9, 9]. I primi tre restano separati. A partire da i, ogni intervallo inizia in corrispondenza o prima di 10, dove termina n, quindi si uniscono in [3, 10], una parte di 8 lettere.
La stringa contiene al massimo 26 lettere diverse, quindi ci sono al massimo 26 intervalli, e le tabelle delle prime e ultime posizioni hanno dimensione fissa.
Algoritmo
- In un'unica scansione di
s, registrafirstelast, la prima e l'ultima posizione di ogni lettera. - Scorri di nuovo
s. Quando la posizioneiè la prima posizione della sua lettera, l'intervallo di quella lettera[i, last]è il successivo nell'ordine di inizio. - Se l'intervallo inizia dopo
enddel blocco corrente, chiudi il blocco, di lunghezzaend-start+1, e avvia un nuovo blocco in corrispondenza dii. - In entrambi i casi, imposta
end = max(end, last). - Chiudi il blocco finale e restituisci le lunghezze.
def partitionLabels(s):
first, last = {}, {}
for i, c in enumerate(s):
first.setdefault(c, i)
last[c] = i
sizes = []
start = end = 0 # the block of merged spans being built
for i, c in enumerate(s):
if first[c] != i:
continue # take each letter's span once, at its first position
if i > end: # this span starts after the block: close the block
sizes.append(end - start + 1)
start = i
end = max(end, last[c])
sizes.append(end - start + 1)
return sizesFai crescere ogni parte fino alla sua ultima lettera
Intuizione
Le prime posizioni non servono affatto. Leggi la stringa da sinistra a destra e mantieni end, la posizione più lontana a destra dell’ultima occorrenza di qualsiasi lettera nella parte corrente. Quando leggi una lettera in i, anche la sua ultima occorrenza deve trovarsi in questa parte, quindi estendi end a last[s[i]] se è più lontano.
Quando i raggiunge end, ogni lettera letta in questa parte ha la sua ultima occorrenza in i o prima. Nessuna lettera oltrepassa il confine dopo i, quindi è consentito tagliare lì. Chiudi la parte, di lunghezza end-start+1, e inizia la successiva da i+1.
Perché tagliare alla prima occasione è la scelta greedy corretta? Prima che i raggiunga end, qualche lettera della parte ha ancora un’occorrenza più a destra, quindi non è consentito alcun taglio precedente. Inoltre, il passaggio non si lascia sfuggire nessun punto di taglio consentito: se nessuna lettera oltrepassa il confine dopo i, ogni lettera della parte termina entro i, quindi proprio lì end è uguale a i. Il passaggio taglia esattamente nei punti consentiti, ottenendo il maggior numero possibile di parti.
In abacdcefe le ultime posizioni sono a 2, b 1, c 5, d 4, e 8 e f 7. Leggere a imposta end a 2, b lo lascia invariato e, a i = 2, la parte si chiude con lunghezza 3. La c imposta end a 5 e la parte si chiude a 5, ancora con lunghezza 3. La parte che contiene e si chiude a 8.
Algoritmo
- In un'unica passata, memorizza
last[c], l'ultima posizione di ogni letterac, in un array di 26 elementi. - Imposta
start = 0eend = 0. - Per ogni posizione
i, impostaend = max(end, last[s[i]]). - Se
i == end, aggiungiend-start+1alla risposta e impostastart = i+1. - Restituisci le lunghezze.
def partitionLabels(s):
last = {c: i for i, c in enumerate(s)} # last position of each letter
sizes = []
start = end = 0
for i, c in enumerate(s):
end = max(end, last[c]) # the part must reach c's last copy
if i == end: # no letter of this part appears later
sizes.append(end - start + 1)
start = i + 1
return sizes
Trappole e casi limite
La passata greedy è breve, quindi i bug si nascondono nella posizione con cui fai il confronto e nella lunghezza delle parti.
- Tagliare quando raggiungi l'ultima occorrenza della lettera corrente invece che l'
enddella parte. Inabcba, la c all'indice 2 è la sua ultima occorrenza, ma le a arrivano fino all'indice 4, quindi un taglio lì separerebbe sia le a sia le b. - Errore di un'unità nella lunghezza. Una parte da
startaend, estremi inclusi, haend-start+1lettere. - Restituire le posizioni dei tagli invece delle lunghezze. Per
abacdcefe, la risposta è[3, 3, 3], non[2, 5, 8]. - Dimenticare l'ultima parte quando tagli in corrispondenza degli spazi. Dopo l'ultima parte non c'è alcuno spazio, quindi aggiungi
n-startuna volta terminato il ciclo. - Aspettarsi una parte per ogni lettera distinta.
zebrazha cinque lettere diverse e una sola parte, perché le z tengono insieme tutto ciò che c'è tra loro.
Domande frequenti4
Qual è la complessità temporale di Partition Labels?
Una passata registra l’ultima posizione di ogni lettera e una seconda passata posiziona i tagli, quindi il tempo è O(n). La tabella delle ultime posizioni ha 26 voci indipendentemente dalla lunghezza della stringa, quindi lo spazio aggiuntivo è O(1), senza contare l’output.
Perché l’approccio greedy funziona per le etichette di partizione?
La parte corrente deve raggiungere l’ultima occorrenza di ogni lettera che contiene, quindi non è consentito alcun taglio prima di end. In end non compare più nessuna lettera della parte, quindi il taglio è consentito e farlo non danneggia mai il resto della stringa. Il passaggio taglia quindi in ogni punto consentito e in nessun altro, ottenendo il maggior numero di parti possibile.
Partition Labels è un problema di fusione di intervalli?
Sì, sotto mentite spoglie. Ogni lettera copre l’intervallo dalla sua prima occorrenza all’ultima, gli intervalli sovrapposti devono condividere una parte e unirli dà esattamente le parti. Il passaggio greedy è la stessa unione eseguita al volo: end è il bordo destro del blocco unito fino a quel momento.
Quante parti può restituire Partition Labels?
Tra 1 e 26. Nessuna lettera può comparire in due parti, quindi ogni parte possiede almeno una lettera propria e ci sono solo 26 lettere minuscole. Una stringa in cui ogni lettera compare una sola volta dà 26 parti di lunghezza 1, mentre una stringa che inizia e finisce con la stessa lettera dà una sola parte.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def partitionLabels(s):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
s = "abacdcefe"
Atteso
[3, 3, 3]