Palindrome String

Q: Come si verifica se una stringa è un palindromo?

Confronta il primo carattere con l’ultimo, il secondo con il penultimo e così via verso il centro. Se una qualsiasi coppia è diversa, la stringa non è un palindromo; se ogni coppia corrisponde, lo è. Due indici che partono da entrambe le estremità e si spostano verso l’interno permettono di farlo in un solo passaggio.

Q: Puoi verificare un palindromo senza memoria aggiuntiva?

Sì. Il controllo con due puntatori legge i caratteri sul posto e memorizza solo due indici, quindi usa O(1) spazio aggiuntivo. Confrontare s con la sua versione invertita è più breve da scrivere, ma crea una seconda stringa di n caratteri.

Q: Qual è la complessità temporale del controllo di una stringa palindroma?

È O(n) per una stringa di lunghezza n . Il controllo con due puntatori esegue al massimo n / 2 confronti e si interrompe alla prima mancata corrispondenza, quindi una stringa i cui caratteri iniziale e finale sono diversi viene determinata dopo un confronto.

Q: Un singolo carattere è un palindromo?

Sì. Una stringa di un solo carattere si legge allo stesso modo in entrambe le direzioni, quindi la risposta è true . Nel ciclo a due puntatori, left e right iniziano entrambi all'indice 0, il ciclo non viene mai eseguito e la funzione restituisce true .

PrincipianteDue puntatori Array e stringhe

+10

Una stringa è un palindromo quando si legge allo stesso modo da sinistra a destra e da destra a sinistra, come level. Scrivi una funzione che riceva una stringa s composta da lettere inglesi minuscole e restituisca true se s è un palindromo e false altrimenti.

Funzione

isPalindrome(s: string) → boolean

sstring: la stringa in minuscolo da controllare
Restituisceboolean: vero quando s si legge allo stesso modo in entrambe le direzioni

Vincoli

1 ≤ s.length ≤ 5 × 10⁴
s contiene solo lettere minuscole dell'alfabeto inglese (da a a z).

Esempi

Input: s = "racecar"
Output: true
Spiegazione: Confronta dall'esterno verso l'interno: r con r, a con a, c con c. La e centrale non ha una compagna e non ne ha bisogno, quindi la risposta è true.

Input: s = "abba"
Output: true
Spiegazione: Con una lunghezza pari, ogni lettera ha una compagna: le due a corrispondono e le due b corrispondono, quindi la risposta è true.

Input: s = "coddy"
Output: false
Spiegazione: La prima lettera c e l’ultima lettera y sono già diverse, quindi coddy non è un palindromo e la risposta è false.

+16 test nascosti all’invio

Per approfondire

Una frase come Was it a car or a cat I saw è un palindromo se ignori maiuscole e minuscole, spazi e punteggiatura. Come modificheresti i due puntatori per saltare quei caratteri?

Suggerimenti

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

0 di 3 aperti

Soluzione

Un palindromo è uguale alla sua versione al contrario, quindi il controllo diretto costruisce la versione al contrario e la confronta. Il controllo migliore non costruisce nulla: il primo carattere deve corrispondere all’ultimo, il secondo al penultimo e così via, procedendo verso il centro. Due indici che avanzano verso l’interno verificano queste coppie sul posto e si fermano alla prima discrepanza.

Confronta la stringa con la sua inversione

Intuizione

Leggere s allo stesso modo in entrambe le direzioni significa che s è uguale alla sua versione invertita. Quindi invertiamola e confrontiamola: racecar invertita è racecar, mentre coddy invertita è yddoc, che è diversa.

Creare la versione invertita e confrontarla richiede di esaminare ogni carattere una volta, quindi il tempo è O(n). La copia invertita contiene altri n caratteri, quindi lo spazio aggiuntivo è O(n): con n = 5 × 10^4 sono 50.000 caratteri creati solo per essere confrontati e poi eliminati.

Inoltre, esegue tutto il lavoro ogni volta. Si capisce se coddy è palindroma dalle sue prime e ultime lettere, eppure questo approccio ne inverte tutte e cinque prima di controllare.

Algoritmo

Costruisci l'inverso di s, usando la funzione di inversione del linguaggio o un ciclo dall'ultimo carattere al primo.
Confronta l'inverso con s.
Restituisci true se sono uguali e false altrimenti.

def isPalindrome(s):
    return s == s[::-1]

Due puntatori da entrambe le estremità

Intuizione

L’inversione sposta il carattere all’indice i all’indice n-1-i, quindi s è uguale alla sua versione invertita esattamente quando s[i] è uguale a s[n-1-i] per ogni i. Ogni coppia compare due volte in quell’elenco, quindi controlla solo la metà sinistra. Imposta left all’indice 0 e right all’indice n-1, confronta i due caratteri e sposta entrambi i puntatori di un passo verso l’interno.

Fermati quando i puntatori si incontrano o si incrociano. In racecar controllano le coppie di indici (0, 6), (1, 5) e (2, 4), poi si incontrano all’indice 3, la e centrale, che non ha bisogno di una compagna. In abba controllano (0, 3) e (1, 2), poi si incrociano. La prima coppia diversa dimostra che la risposta è false, quindi restituisci il risultato immediatamente: il caso coddy si risolve dopo un solo confronto.

Si eseguono al massimo n / 2 confronti, ovvero un tempo O(n), e l’unica memoria utilizzata è quella di due indici, cioè spazio O(1). R fa eccezione: prima legge la stringa come un vettore di codici carattere, operazione che costa O(n).

Algoritmo

Imposta left = 0 e right = n-1.
Mentre left < right, confronta s[left] con s[right].
Se sono diversi, restituisci false.
Altrimenti aggiungi 1 a left, sottrai 1 da right e ripeti.
Quando i puntatori si incontrano o si incrociano, ogni coppia corrisponde: restituisci true.

def isPalindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

Trappole e casi limite

Il ciclo è breve, quindi gli errori si trovano nei suoi limiti e nelle sue istruzioni return.

Restituire true non appena una coppia corrisponde. abca supera il confronto della coppia esterna e non supera quello della coppia interna, quindi true può essere restituito solo dopo la fine del ciclo.
Iniziare right da n invece che da n-1, leggendo oltre la fine (in C, oltre il terminatore '\0'). In Lua e R gli indici vanno da 1 a n, quindi lì right parte da n.
Confrontare le stringhe tramite indirizzo. In C, reversed == s confronta due puntatori ed è sempre falso per una copia appena creata; usa strcmp.
Costruire la stringa inversa con result = result + ch in un ciclo. A ogni passaggio viene copiata l'intera stringa costruita fin lì: circa 1.25 × 10^9 copie di caratteri per 50,000 lettere.
Indicizzare una stringa Swift con un intero. Il codice non viene compilato; percorri s.utf8 usando i suoi indici oppure copia i caratteri in un array.

Domande frequenti4

Come si verifica se una stringa è un palindromo?

Confronta il primo carattere con l’ultimo, il secondo con il penultimo e così via verso il centro. Se una qualsiasi coppia è diversa, la stringa non è un palindromo; se ogni coppia corrisponde, lo è. Due indici che partono da entrambe le estremità e si spostano verso l’interno permettono di farlo in un solo passaggio.

Puoi verificare un palindromo senza memoria aggiuntiva?

Sì. Il controllo con due puntatori legge i caratteri sul posto e memorizza solo due indici, quindi usa O(1) spazio aggiuntivo. Confrontare s con la sua versione invertita è più breve da scrivere, ma crea una seconda stringa di n caratteri.

Qual è la complessità temporale del controllo di una stringa palindroma?

È O(n) per una stringa di lunghezza n. Il controllo con due puntatori esegue al massimo n / 2 confronti e si interrompe alla prima mancata corrispondenza, quindi una stringa i cui caratteri iniziale e finale sono diversi viene determinata dopo un confronto.

Un singolo carattere è un palindromo?

Sì. Una stringa di un solo carattere si legge allo stesso modo in entrambe le direzioni, quindi la risposta è true. Nel ciclo a due puntatori, left e right iniziano entrambi all'indice 0, il ciclo non viene mai eseguito e la funzione restituisce true.

Python

def isPalindrome(s):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

s = "racecar"

Atteso

true