Reverse a String

Q: Qual è la complessità temporale dell'inversione di una stringa?

Invertire richiede un tempo O(n) , perché ogni carattere deve spostarsi in una nuova posizione e viene gestito una sola volta. Creare una nuova stringa richiede uno spazio aggiuntivo pari a O(n) . Lo scambio con due puntatori richiede solo uno spazio aggiuntivo pari a O(1) quando i caratteri si trovano già in un array mutabile.

Q: Come si inverte una stringa senza una funzione di inversione integrata?

Copia i caratteri in un array, posiziona un puntatore a ciascuna estremità, scambia i due caratteri e sposta i puntatori l'uno verso l'altro finché non si incontrano. In alternativa, scorri gli indici dall'ultimo al primo e aggiungi ogni carattere a un builder. Entrambi producono la stringa invertita in un'unica passata.

Q: Riesci a invertire una stringa sul posto?

Solo quando i caratteri si trovano in un buffer modificabile, come un array di char in C, Java o C#, una lista in Python oppure una std::string in C++. Le stringhe in Java, Python, JavaScript e molti altri linguaggi sono immutabili, quindi le copi in un array, scambi i caratteri al suo interno e crei una nuova stringa. In entrambi i casi, lo scambio in sé avviene sul posto.

Q: Perché il ciclo a due puntatori si ferma a metà?

Ogni scambio colloca due caratteri nelle loro posizioni finali, quindi dopo n / 2 scambi ogni carattere si trova al posto giusto. Continuare oltre la metà scambia di nuovo le stesse coppie e annulla il lavoro svolto. Quando la lunghezza è dispari, il carattere centrale si trova già al proprio indice speculare e non ha bisogno di essere scambiato.

PrincipianteArray e stringhe Due puntatori

+10

Ricevi una stringa s composta da lettere inglesi e cifre. Restituisci una nuova stringa con gli stessi caratteri in ordine inverso, in modo che l’ultimo carattere venga per primo e il primo per ultimo. Mantieni ogni carattere esattamente com’è, inclusa la distinzione tra maiuscole e minuscole.

Funzione

reverseString(s: string) → string

sstring: la stringa da invertire
Restituiscestring: i caratteri di s in ordine inverso

Vincoli

1 ≤ s.length ≤ 10⁴
s contiene solo lettere inglesi (a–z, A–Z) e cifre (0–9).

Esempi

Input: s = "Coddy2026"
Output: "6202yddoC"
Spiegazione: Leggi Coddy2026 dall’ultimo carattere al primo: 6, 2, 0, 2, poi y, d, d, o e infine la C maiuscola.

Input: s = "noon"
Output: "noon"
Spiegazione: noon è un palindromo, quindi il suo inverso è la stessa parola. Le n esterne si scambiano di posto, poi lo fanno le due o.

+14 test nascosti all’invio

Per approfondire

Come invertiresti l’ordine delle parole in una frase, trasformando hello big world in world big hello, mantenendo l’ordine delle lettere in ogni parola?

Suggerimenti

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

0 di 3 aperti

Soluzione

Ogni carattere ha una destinazione fissa: quello all'indice i va all'indice n-1-i. Puoi scrivere i caratteri in una nuova stringa in quest'ordine oppure scambiarli a coppie partendo da entrambe le estremità. Lo scambio è la versione richiesta nei colloqui, perché lo stesso movimento con due puntatori inverte un array sul posto e verifica se è palindromo.

Copia i caratteri dal retro

Intuizione

L'inverso di s inizia con l'ultimo carattere di s, continua con il penultimo e termina con il primo. Quindi scorri un indice da n-1 fino a 0 e aggiungi ogni carattere alla risposta man mano che lo incontri. Per Coddy2026 aggiungi 6, 2, 0, 2, y e così via, ottenendo 6202yddoC.

Ogni carattere viene letto una volta e scritto una volta, quindi il lavoro è O(n). La risposta è una seconda stringa di n caratteri, quindi lo spazio aggiuntivo è O(n).

Il modo in cui aggiungi i caratteri è importante. Aggiungere un carattere a una stringa immutabile con + copia l'intera stringa ogni volta e, per n = 10^4, questo comporta circa 5 × 10^7 copie di caratteri. Raccogli i caratteri in una lista o in un generatore di stringhe e uniscili una sola volta alla fine.

Algoritmo

Crea una lista vuota o un generatore di stringhe per la risposta.
Esegui un ciclo su i da n-1 a 0 in ordine decrescente.
Aggiungi s[i] alla risposta.
Unisci la risposta in una stringa e restituiscila.

def reverseString(s):
    result = []
    for i in range(len(s) - 1, -1, -1):
        result.append(s[i])
    return "".join(result)

Scambia partendo da entrambe le estremità con due puntatori

Intuizione

Invertire scambia le coppie di caratteri procedendo dall’esterno verso il centro. Il primo e l’ultimo si scambiano di posto, poi il secondo e il penultimo, e così via verso il centro. Posiziona un puntatore left sull’indice 0 e un puntatore right sull’indice n-1, scambia i due caratteri e sposta entrambi i puntatori di un passo verso l’interno.

Fermati quando i puntatori si incontrano o si incrociano. In noon i puntatori partono da 0 e 3, poi passano a 1 e 2, quindi si incrociano, dopo due scambi. Con una lunghezza dispari, come in xYz, si incontrano sul carattere centrale, che si trova già nella sua posizione finale, quindi non viene mai toccato. Ogni scambio mette due caratteri nelle loro posizioni finali, quindi n / 2 scambi completano il lavoro.

Gli scambi richiedono soltanto una variabile temporanea, cioè spazio aggiuntivo O(1). La maggior parte dei linguaggi non consente di modificare una stringa sul posto, quindi prima la copi in un array di caratteri, operazione che richiede O(n). In un colloquio in cui l’input è già un array di caratteri, questo approccio lo inverte senza usare memoria aggiuntiva.

Algoritmo

Copia s in un array di caratteri.
Imposta left = 0 e right = n-1.
Finché left < right, scambia i caratteri in corrispondenza di left e right, poi aggiungi 1 a left e sottrai 1 da right.
Trasforma di nuovo l’array in una stringa e restituiscila.

def reverseString(s):
    chars = list(s)
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    return "".join(chars)

Trappole e casi limite

L’inversione sembra richiedere una sola riga, ma gli errori si nascondono nei limiti del ciclo e nel modo in cui viene costruita la risposta.

Far avanzare il ciclo di left fino a n-1. Superata la metà, ogni coppia viene scambiata una seconda volta e la stringa torna invariata. Fermati a left < right.
Iniziare il ciclo all’indietro da n invece che da n-1, leggendo così una posizione oltre la fine. In Lua e R gli indici vanno invece da 1 a n.
Costruire la risposta con result = result + ch su una stringa immutabile. A ogni passaggio viene copiato tutto il contenuto accumulato, trasformando un’operazione lineare in una quadratica sugli input lunghi.
Dimenticare il terminatore '\0' in C. Un buffer di n byte è troppo corto di un byte: allocane n + 1.
Scambiare senza una variabile temporanea: dopo chars[left] = chars[right] il carattere originale a sinistra è perso, a meno che il tuo linguaggio non scambi entrambi i valori contemporaneamente.

Domande frequenti4

Qual è la complessità temporale dell'inversione di una stringa?

Invertire richiede un tempo O(n), perché ogni carattere deve spostarsi in una nuova posizione e viene gestito una sola volta. Creare una nuova stringa richiede uno spazio aggiuntivo pari a O(n). Lo scambio con due puntatori richiede solo uno spazio aggiuntivo pari a O(1) quando i caratteri si trovano già in un array mutabile.

Come si inverte una stringa senza una funzione di inversione integrata?

Copia i caratteri in un array, posiziona un puntatore a ciascuna estremità, scambia i due caratteri e sposta i puntatori l'uno verso l'altro finché non si incontrano. In alternativa, scorri gli indici dall'ultimo al primo e aggiungi ogni carattere a un builder. Entrambi producono la stringa invertita in un'unica passata.

Riesci a invertire una stringa sul posto?

Solo quando i caratteri si trovano in un buffer modificabile, come un array di char in C, Java o C#, una lista in Python oppure una std::string in C++. Le stringhe in Java, Python, JavaScript e molti altri linguaggi sono immutabili, quindi le copi in un array, scambi i caratteri al suo interno e crei una nuova stringa. In entrambi i casi, lo scambio in sé avviene sul posto.

Perché il ciclo a due puntatori si ferma a metà?

Ogni scambio colloca due caratteri nelle loro posizioni finali, quindi dopo n / 2 scambi ogni carattere si trova al posto giusto. Continuare oltre la metà scambia di nuovo le stesse coppie e annulla il lavoro svolto. Quando la lunghezza è dispari, il carattere centrale si trova già al proprio indice speculare e non ha bisogno di essere scambiato.

Python

def reverseString(s):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

s = "Coddy2026"

Atteso

"6202yddoC"