Verificare correttamente i palindromi
Confrontare in modo efficiente le due estremità
Verificare correttamente i palindromi è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Che cos'è un palindromo
Un palindromo si legge allo stesso modo da sinistra a destra e da destra a sinistra, come racecar o level. Verificarlo è un classico esercizio introduttivo. 🔁
Il trucco dello slicing
Python può invertire una stringa con lo slice s[::-1]. La confronti con l'originale e avrà un controllo in una sola riga.
s = 'level'
print(s == s[::-1]) # TrueLo slicing usa memoria aggiuntiva
Il metodo dello slice è breve, ma crea una copia completa invertita. Per stringhe enormi, questa memoria aggiuntiva può essere importante con limiti restrittivi.
Il metodo dei due puntatori
Posizioni un puntatore all'inizio e uno alla fine. Li confronti e li sposti verso il centro. Questo usa O(1) di spazio aggiuntivo.
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]:
break
i += 1; j -= 1Fermarsi al centro
I puntatori devono soltanto incontrarsi a metà. Quando i non è minore di j, ogni coppia ha trovato corrispondenza e la stringa è un palindromo.
Una differenza significa fermarsi subito
Il ciclo con due puntatori può restituire False non appena una coppia differisce. Raramente dovrà scorrere l'intera stringa, con un buon vantaggio in termini di velocità.
def is_pal(s):
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]: return False
i += 1; j -= 1
return TrueEntrambi sono O(n)
In entrambi i casi ogni carattere viene esaminato al massimo una volta, quindi entrambi i metodi hanno tempo lineare. Differiscono soltanto per la memoria aggiuntiva utilizzata.
Normalizzare prima
Molti problemi ignorano maiuscole, minuscole e spazi. Pulisca la stringa prima, convertendola in minuscolo e conservando soltanto lettere e cifre.
raw = 'A man, a plan'
clean = ''.join(c.lower() for c in raw if c.isalnum())Poi controllare la stringa pulita
Una volta normalizzata, esegua il consueto controllo di palindromo sulla versione pulita. È lo schema standard per i palindromi nelle frasi.
print(clean == clean[::-1])I puntatori saltano le lettere non valide
Invece di pulire prima la stringa, due puntatori possono saltare sul posto qualsiasi carattere non alfanumerico. In questo modo evita completamente di creare una seconda stringa.
Palindromi nelle sottostringhe
I problemi più complessi chiedono informazioni sulle sottostringhe palindrome. L'idea fondamentale è espandere attorno al centro: si procede verso l'esterno da ogni posizione finché le estremità coincidono.
Verifica rapida
Una domanda sui controlli dei palindromi.
Riepilogo
Ora sa verificare i palindromi con un rapido slice o con due puntatori che usano poca memoria, oltre a normalizzare l'input disordinato prima del controllo. 🎉
Domande Frequenti
La lezione «Verificare correttamente i palindromi» è gratuita?
Sì — il testo completo di «Verificare correttamente i palindromi» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Verificare correttamente i palindromi»?
Confrontare in modo efficiente le due estremità Eserciti Competitive Programming Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Verificare correttamente i palindromi»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Trucchi con caratteri, ord e chr
- Contare le lettere con una tabella delle frequenze
- Verificare correttamente i palindromi
- Dividere, ripulire e ricomporre le parole