Reverse Words in a String

Q: Qual è la complessità temporale di Reverse Words in a String?

Entrambi gli approcci richiedono un tempo O(n) per una stringa di lunghezza n , perché ogni carattere viene letto e scritto un numero costante di volte. La suddivisione richiede O(n) di spazio aggiuntivo per l’elenco delle parole. Invertire l’intera stringa e poi ogni parola richiede O(1) di spazio aggiuntivo su un array di caratteri che puoi modificare.

MedioArray e stringhe Due puntatori

+10

Ricevi una stringa s composta da parole e spazi. Una parola è una sequenza di lettere e cifre senza spazi al suo interno. Le parole possono essere separate da più di uno spazio e s può iniziare o terminare con spazi.

Restituisci le parole in ordine inverso, unite da esattamente uno spazio, senza spazi all'inizio o alla fine. Ogni parola mantiene la propria grafia; cambia solo l'ordine delle parole.

Funzione

reverseWords(s: string) → string

sstring: lettere, cifre e spazi contenenti almeno una parola
Restituiscestring: le parole di s in ordine inverso, separate da singoli spazi

Vincoli

1 ≤ s.length ≤ 10⁴
s contiene solo lettere inglesi, cifre e spazi.
s contiene almeno una parola.

Esempi

Input: s = "Coddy runs in 15 languages"
Output: "languages 15 in runs Coddy"
Spiegazione: Le parole sono Coddy, runs, in, 15 e languages. Letti dall'ultimo al primo, formano languages 15 in runs Coddy; 15 conta come una parola perché le parole possono contenere cifre.

Input: s = " practice makes progress "
Output: "progress makes practice"
Spiegazione: Gli spazi a entrambe le estremità vengono eliminati e le sequenze di due e tre spazi tra le parole si riducono a uno. Le tre parole vengono restituite dall’ultima alla prima: progress makes practice.

Input: s = " single "
Output: "single"
Spiegazione: Una lista di una parola si legge allo stesso modo al contrario. Vengono rimossi solo gli spazi intorno, quindi la risposta è single.

Per approfondire

Puoi invertire le parole ma mantenere la spaziatura di s: le stesse sequenze di spazi, con le stesse lunghezze, nello stesso ordine?

Soluzione

L’ordine delle parole è un’inversione; gli spazi sono il punto in cui le soluzioni si inceppano. Gli spazi all’inizio o alla fine e gli spazi ripetuti tra le parole devono scomparire, lasciando esattamente uno spazio tra le parole nella risposta. Puoi suddividere la stringa in un elenco di parole oppure invertire l’intera stringa e poi ogni parola all’interno di un unico array.

Dividi in parole e uniscile al contrario

Intuizione

Dividi s nelle sue parole, inverti l’elenco e uniscilo con spazi singoli. La divisione richiede attenzione: dividendo " practice makes progress " a ogni singolo spazio si ottengono sei elementi vuoti attorno alle tre parole. Elimina gli elementi vuoti e l’elenco è practice, makes, progress.

La divisione legge ogni carattere una volta e l’unione scrive una volta ogni carattere mantenuto, quindi il tempo è O(n) per una stringa di lunghezza n. L’elenco delle parole e la risposta richiedono O(n) spazio aggiuntivo.

Algoritmo

Dividi s sugli spazi.
Elimina le parti vuote.
Inverti l’elenco delle parole.
Unisci le parole con uno spazio tra ciascuna e restituisci il risultato.

def reverseWords(s):
    # split() with no argument treats any run of spaces as one separator
    # and ignores spaces at both ends.
    words = s.split()
    words.reverse()
    return " ".join(words)

Inverti l'intera stringa, poi ogni parola

Intuizione

Invertire l'intera stringa mette le parole nell'ordine giusto, ma scrive ciascuna al contrario: Coddy runs in 15 languages diventa segaugnal 51 ni snur yddoC. Invertendo poi ogni parola per conto proprio si ottiene languages 15 in runs Coddy.

Gli spazi vengono gestiti nello stesso passaggio. Un indice read attraversa l'array invertito e salta gli spazi; un indice write indica dove va il prossimo carattere da mantenere. La copia non sovrascrive mai un carattere di cui hai ancora bisogno, perché write non supera mai read: lo spazio scritto prima di una parola sostituisce almeno uno spazio saltato da read.

Ogni carattere viene copiato al massimo una volta e scambiato al massimo due volte, quindi il tempo è O(n), con spazio aggiuntivo O(1) su un buffer di caratteri che puoi modificare. Qui le stringhe arrivano come valori, quindi ogni soluzione crea una copia di lavoro di s: O(n) di memoria in totale.

Algoritmo

Copia s in un array di caratteri e inverti l'intero array.
Scorri l'array con un indice di lettura e salta gli spazi.
Per ogni parola, scrivi prima uno spazio, a meno che non sia la prima parola, poi copia i caratteri della parola all'indice di scrittura.
Inverti la porzione copiata in modo che la parola si legga nel verso giusto.
Restituisci i primi write caratteri.

def reverseWords(s):
    chars = list(s)

    def reverse(lo, hi):
        while lo < hi:
            chars[lo], chars[hi] = chars[hi], chars[lo]
            lo += 1
            hi -= 1

    n = len(chars)
    reverse(0, n - 1)  # words in the right order, each spelled backwards
    write = 0
    read = 0
    while read < n:
        if chars[read] == " ":
            read += 1
            continue
        if write > 0:
            chars[write] = " "  # one space before every word but the first
            write += 1
        start = write
        while read < n and chars[read] != " ":
            chars[write] = chars[read]
            write += 1
            read += 1
        reverse(start, write - 1)  # spell the word forwards again
    return "".join(chars[:write])

Trappole e casi limite

Dividere usando un singolo spazio e mantenere ogni parte. "a b" si divide in a, una parte vuota e b, e l'unione ripristina due spazi: "b a".
Confidare nel fatto che la divisione elimini gli spazi alle estremità. split(" ") di Java elimina le parti vuote alla fine, ma le mantiene all'inizio, quindi " a b" ne lascia ancora una.
Aggiungere uno spazio dopo ogni parola, inclusa l'ultima, così la risposta termina con uno spazio. Metti lo spazio prima di ogni parola, tranne la prima.
Eseguire una sola inversione nella versione in-place. Invertendo solo le parole si ottiene yddoC snur ni 51 segaugnal.
In PHP e R, un input composto solo da cifre, come 2026, può arrivare come numero. Convertirlo in una stringa prima di dividerlo.

Domande frequenti3

Qual è la complessità temporale di Reverse Words in a String?

Entrambi gli approcci richiedono un tempo O(n) per una stringa di lunghezza n, perché ogni carattere viene letto e scritto un numero costante di volte. La suddivisione richiede O(n) di spazio aggiuntivo per l’elenco delle parole. Invertire l’intera stringa e poi ogni parola richiede O(1) di spazio aggiuntivo su un array di caratteri che puoi modificare.

Come si gestiscono più spazi tra le parole?

Considera una parola come una sequenza di caratteri non-spazio e non copiare mai gli spazi dall’input. Uno split senza separatore in Python e Ruby, strings.Fields in Go e split_whitespace in Rust saltano già ogni sequenza di spazi e gli spazi a entrambe le estremità; altrove, elimina le parti vuote. Poi inserisci uno spazio tra le parole.

Riesci a invertire le parole senza una funzione split?

Sì. Scansiona dall'estremità destra: salta gli spazi, segna dove termina una parola, spostati a sinistra fino al suo inizio e aggiungi la parola preceduta da uno spazio, a meno che non sia la prima. Ogni carattere viene visitato una volta, quindi il tempo resta O(n), e le parole risultano in ordine inverso senza dover invertire alcuna lista.

def reverseWords(s):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

s = "Coddy runs in 15 languages"

Output atteso

"languages 15 in runs Coddy"