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. Due indici che partono da entrambe le estremità e si spostano verso l’interno eseguono questa operazione in un’unica passata.

Q: Riesci a verificare se una parola è palindroma senza usare memoria aggiuntiva?

Sì. Il controllo con due puntatori legge i caratteri sul posto e memorizza 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 della verifica di una stringa palindroma?

O(n) per una stringa di lunghezza n . Il controllo con due puntatori effettua al massimo n / 2 confronti e si ferma alla prima discordanza, quindi coddy richiede un confronto.

Q: Un singolo carattere è un palindromo?

Sì, si legge allo stesso modo in entrambe le direzioni. 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 riceve una stringa s composta da lettere inglesi minuscole e restituisce true se s è un palindromo e false altrimenti.

Funzione

isPalindrome(s: string) → boolean

sstring: la stringa minuscola 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 inglesi (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 un elemento corrispondente 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.

Per approfondire

Come modificheresti i due puntatori per saltare gli spazi e la punteggiatura e ignorare le maiuscole e le minuscole, in modo che Was it a car or a cat I saw venga considerata una palindroma?

Suggerimenti

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

0 di 3 aperti

Soluzione

Un palindromo è uguale al suo inverso, quindi puoi costruire l’inverso e confrontarlo. Non ti serve la copia: il primo carattere deve corrispondere all’ultimo, il secondo al penultimo e così via. Due indici che avanzano verso l’interno verificano queste coppie sul posto e si fermano alla prima mancata corrispondenza.

Confronta la stringa con la sua versione invertita

Intuizione

Inverti s e confrontala: racecar invertita è racecar, mentre coddy invertita è yddoc. Una stringa si legge allo stesso modo in entrambe le direzioni esattamente quando è uguale alla sua inversa.

Il tempo è O(n), ma la copia invertita richiede O(n) spazio aggiuntivo, 50.000 caratteri con n = 5 × 10^4. Anche il lavoro è sempre completo: coddy si determina dalle prime e ultime lettere, eppure prima vengono invertite tutte e cinque.

Algoritmo

Costruisci l'inversa di s, usando la funzione di inversione del linguaggio o un ciclo dall'ultimo carattere al primo.
Confronta l'inversa 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 l'indice i all'indice n-1-i, quindi s è uguale alla sua inversa esattamente quando s[i] è uguale a s[n-1-i] per ogni i. Ogni coppia compare due volte in questa condizione, quindi è sufficiente controllare la metà sinistra. In racecar le coppie sono (0, 6), (1, 5) e (2, 4); la e centrale all'indice 3 non ha bisogno di una compagna.

La prima coppia diversa dimostra che la risposta è false, quindi per coddy si decide dopo un solo confronto. Vengono eseguiti al massimo n / 2 confronti: tempo O(n), e due indici richiedono spazio O(1). R legge prima la stringa come vettore di codici carattere, operazione che richiede O(n).

Algoritmo

Imposta left = 0 e right = n-1.
Finché 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 ha trovato corrispondenza: 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

Restituire true non appena una coppia corrisponde. abca supera la coppia esterna e non supera quella interna, quindi true arriva solo dopo il ciclo.
Impostare right a n invece che a n-1, il che legge oltre la fine (in C, il terminatore '\0'). In Lua e R gli indici vanno da 1 a n, quindi lì right parte da n.
Confrontare stringhe con == in C. reversed == s confronta due puntatori ed è falso per una copia; usa strcmp.
Costruire il rovescio con result = result + ch. A ogni passaggio viene copiata la stringa fin lì: circa 1.25 × 10^9 copie di caratteri per 50,000 lettere.
Indicizzare una stringa Swift con un intero: non compila. Scorri s.utf8 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. Due indici che partono da entrambe le estremità e si spostano verso l’interno eseguono questa operazione in un’unica passata.

Riesci a verificare se una parola è palindroma senza usare memoria aggiuntiva?

Sì. Il controllo con due puntatori legge i caratteri sul posto e memorizza 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 della verifica di una stringa palindroma?

O(n) per una stringa di lunghezza n. Il controllo con due puntatori effettua al massimo n / 2 confronti e si ferma alla prima discordanza, quindi coddy richiede un confronto.

Un singolo carattere è un palindromo?

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

def isPalindrome(s):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

s = "racecar"

Output atteso

true