Valid Palindrome

Q: Qual è la complessità temporale di Valid Palindrome?

Entrambi gli approcci hanno una complessità temporale di O(n) , perché ogni carattere viene esaminato un numero costante di volte. Prima ripulire la stringa richiede O(n) di memoria aggiuntiva per la copia. La versione con due puntatori usa O(1) di memoria aggiuntiva, perché mantiene solo due indici.

Q: Come si verifica un palindromo ignorando i caratteri non alfanumerici?

Mantieni un puntatore a ciascuna estremità della stringa. Sposta un puntatore oltre ogni carattere che non sia una lettera o una cifra e, quando entrambi si trovano su lettere o cifre, confrontali in minuscolo. Se tutte le coppie confrontate corrispondono fino a quando i puntatori si incontrano, la stringa è un palindromo.

Q: Una stringa vuota è un palindromo?

Sì. Un testo vuoto si legge allo stesso modo in entrambe le direzioni, quindi una stringa come ?!-_ , i cui caratteri vengono tutti ignorati, restituisce true . Entrambi gli approcci ottengono questo risultato senza codice aggiuntivo: il testo ripulito è uguale al suo inverso vuoto e i due puntatori non trovano mai una coppia di caratteri diversi.

Q: Perché usare due puntatori invece di invertire la stringa?

Invertire richiede una copia ripulita e una copia invertita, ovvero O(n) di memoria aggiuntiva. Due puntatori confrontano le stesse coppie sul posto e possono fermarsi alla prima discrepanza, spesso dopo pochi passaggi. Durante i colloqui, di solito gli intervistatori chiedono questa versione come domanda di approfondimento.

FacileDue puntatori

+10

Ti viene data una stringa s. Mantieni solo le lettere e le cifre, considera le maiuscole e le minuscole come la stessa lettera e determina se ciò che rimane si legge allo stesso modo da sinistra a destra e da destra a sinistra. Restituisci true se è così e false in caso contrario.

Tutti gli altri caratteri, come ., !, ?, :, ;, - o _, vengono ignorati. Se s non contiene lettere o cifre, non rimane nulla e un testo vuoto è considerato un palindromo.

Funzione

isPalindrome(s: string) → boolean

sstring: il testo da controllare, punteggiatura inclusa
Restituisceboolean: true se le lettere e le cifre di s si leggono allo stesso modo in entrambe le direzioni, ignorando maiuscole e minuscole

Vincoli

1 ≤ s.length ≤ 5 × 10⁴
s contiene lettere inglesi, cifre e i segni di punteggiatura . ! ? : ; - _, senza spazi.

Esempi

Input: s = "Was_it_a_car_or_a_cat_I_saw?"
Output: true
Spiegazione: Elimina i trattini bassi e il punto interrogativo e trasforma le lettere maiuscole in minuscole: ottieni wasitacaroracatisaw, che è uguale al contrario.

Input: s = "race-a-car"
Output: false
Spiegazione: Senza i trattini, il testo è raceacar. Letto da destra, inizia con raca invece che con race: la e al centro ha una a come elemento speculare, quindi la risposta è false.

Input: s = "Step-on-no-pets!"
Output: true
Spiegazione: Il testo mantenuto è steponnopets. La S maiuscola corrisponde alla s finale perché le maiuscole e le minuscole vengono ignorate, e i trattini e ! non hanno alcun ruolo.

+25 test nascosti all’invio

Per approfondire

Riesci a deciderlo usando memoria aggiuntiva O(1), senza creare una copia ripulita di s?

Suggerimenti

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

0 di 3 aperti

Soluzione

Il controllo del palindromo in sé è quello consueto: il primo carattere conservato deve essere uguale all’ultimo, il secondo deve essere uguale al penultimo, e così via. Ciò che rende complicata questa versione è che i caratteri da confrontare non si trovano in indici speculari di s, perché la punteggiatura è distribuita in modo irregolare sui due lati. Puoi rimuoverla prima oppure lasciare che due puntatori la saltino mentre si avvicinano l’uno all’altro.

Pulisci la stringa, poi confrontala con la sua inversa

Intuizione

Costruisci il testo a cui il problema fa effettivamente riferimento. Scorri s, mantieni ogni lettera o cifra in minuscolo e ignora tutto il resto. Per Step-on-no-pets! ottieni steponnopets. Ora la domanda è quella semplice sul palindromo: questo testo è uguale al suo inverso?

Questo è corretto perché la pulizia rimuove esattamente i caratteri che il problema dice di ignorare e converte in minuscolo le lettere di cui dice di ignorare la distinzione tra maiuscole e minuscole. Se s non contiene lettere o cifre, il testo ripulito è vuoto e un testo vuoto è uguale al suo inverso, quindi la risposta è true senza casi speciali.

Ogni carattere viene letto una volta per la pulizia e un'altra volta per il confronto, quindi il tempo è O(n). La copia ripulita e il suo inverso richiedono O(n) di memoria aggiuntiva, che è il costo eliminato dall'approccio successivo.

Algoritmo

Crea un testo vuoto cleaned.
Per ogni carattere di s, se è una lettera o una cifra, aggiungilo in minuscolo.
Inverti cleaned.
Restituisci se cleaned è uguale alla sua versione invertita.

def isPalindrome(s):
    cleaned = [ch.lower() for ch in s if ch.isalnum()]
    return cleaned == cleaned[::-1]

Due puntatori che saltano la punteggiatura

Intuizione

La copia ripulita serve solo per confrontare i caratteri speculari. Puoi fare lo stesso confronto direttamente su s. Imposta left sull’indice iniziale e right su quello finale. A ogni passaggio, se left punta alla punteggiatura, spostalo a destra; se right punta alla punteggiatura, spostalo a sinistra. Quando entrambi puntano a lettere o cifre, confrontali in minuscolo. Una mancata corrispondenza significa false; se corrispondono, entrambi i puntatori avanzano verso l’interno.

Perché è lo stesso controllo? I puntatori si fermano sempre sul successivo carattere conservato procedendo da ciascuna estremità, quindi visitano le coppie (primo carattere conservato, ultimo carattere conservato), (secondo carattere conservato, penultimo carattere conservato) e così via: esattamente le coppie considerate dal confronto con la stringa invertita. In Abc-dcbX la prima coppia è A e X, e la risposta è false dopo un solo confronto.

A ogni passaggio si sposta almeno un puntatore, e i puntatori si fermano quando si incontrano, quindi il ciclo viene eseguito al massimo n volte. A parte i due indici, non viene memorizzato nulla, il che comporta un uso di memoria aggiuntiva pari a O(1).

Algoritmo

Imposta left = 0 e right = n-1.
Mentre left < right: se s[left] non è una lettera o una cifra, incrementa left e continua.
Altrimenti, se s[right] non è una lettera o una cifra, decrementa right e continua.
Altrimenti confronta i due caratteri in minuscolo. Se sono diversi, restituisci false; se corrispondono, sposta entrambi i puntatori verso l'interno.
Quando i puntatori si incontrano, restituisci true.

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

Trappole e casi limite

La maggior parte dei bug deriva dai caratteri che vengono ignorati e dalla distinzione tra maiuscole e minuscole.

Confrontare s[i] con s[n-1-i] nella stringa originale. a-ba è un palindromo una volta eliminato il trattino, ma il riflesso del carattere - all’indice 1 nella stringa originale è la b all’indice 2.
Spostare entrambi i puntatori quando solo uno dei due si trova su un segno di punteggiatura. Ignora un lato alla volta, altrimenti i due lati non saranno più allineati.
Ignorare i segni di punteggiatura in un ciclo interno che supera l’altro puntatore. Con ?!-_, un ciclo interno senza limiti supera la fine della stringa; controlla left < right a ogni spostamento.
Considerare le cifre come rumore. 0P è false: la cifra 0 viene mantenuta e confrontata, e non è la lettera p.
Restituire false quando non viene mantenuto nulla. Una stringa composta solo da segni di punteggiatura, come ., ha un testo ripulito vuoto, che è un palindromo.
Una stringa composta solo da cifre, come 12321, può essere interpretata come un numero da PHP e R. Convertirla prima in una stringa.

Domande frequenti4

Qual è la complessità temporale di Valid Palindrome?

Entrambi gli approcci hanno una complessità temporale di O(n), perché ogni carattere viene esaminato un numero costante di volte. Prima ripulire la stringa richiede O(n) di memoria aggiuntiva per la copia. La versione con due puntatori usa O(1) di memoria aggiuntiva, perché mantiene solo due indici.

Come si verifica un palindromo ignorando i caratteri non alfanumerici?

Mantieni un puntatore a ciascuna estremità della stringa. Sposta un puntatore oltre ogni carattere che non sia una lettera o una cifra e, quando entrambi si trovano su lettere o cifre, confrontali in minuscolo. Se tutte le coppie confrontate corrispondono fino a quando i puntatori si incontrano, la stringa è un palindromo.

Una stringa vuota è un palindromo?

Sì. Un testo vuoto si legge allo stesso modo in entrambe le direzioni, quindi una stringa come ?!-_, i cui caratteri vengono tutti ignorati, restituisce true. Entrambi gli approcci ottengono questo risultato senza codice aggiuntivo: il testo ripulito è uguale al suo inverso vuoto e i due puntatori non trovano mai una coppia di caratteri diversi.

Perché usare due puntatori invece di invertire la stringa?

Invertire richiede una copia ripulita e una copia invertita, ovvero O(n) di memoria aggiuntiva. Due puntatori confrontano le stesse coppie sul posto e possono fermarsi alla prima discrepanza, spesso dopo pochi passaggi. Durante i colloqui, di solito gli intervistatori chiedono questa versione come domanda di approfondimento.

Python

def isPalindrome(s):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

s = "Was_it_a_car_or_a_cat_I_saw?"

Atteso

true