Verificare se una stringa è un palindromo (si legge uguale da sinistra a destra e da destra a sinistra) è un classico esercizio di programmazione e domanda da colloquio. Testa manipolazione stringhe, cicli, complessità algoritmica. Ecco due approcci e implementazioni in Java e Python.
Cos'è un palindromo
Parola o frase che resta identica se letta al contrario. Esempi: "radar", "level", "anna", "osso". "padre" non lo è. Il termine deriva dal greco palin (ancora) + dromos (strada), coniato da Ben Jonson (1600).
Approccio 1: Inversione e confronto (O(n))
Inverti la stringa e confronta con l'originale. Semplice ma sempre O(n) anche se il primo carattere differisce.
Python
def is_palindrome(s):
return s == s[::-1]
# Test
print(is_palindrome("radar")) # True
print(is_palindrome("padre")) # False
Java
public static boolean isPalindrome(String s) {
return new StringBuilder(s).reverse().toString().equals(s);
}
Approccio 2: Due puntatori (O(n/2) → O(n), ma early exit)
Confronta primo e ultimo carattere, poi secondo e penultimo, ecc. Fermati alla prima differenza. Migliore nel caso medio.
Python
def is_palindrome_two_pointers(s):
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
Java
public static boolean isPalindromeTwoPointers(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) return false;
left++; right--;
}
return true;
}
Considerazioni importanti
- Case-sensitive? "Anna" vs "anna". Chiedi al colloquiatore. Per case-insensitive:
s.lower()(Python) os.toLowerCase()(Java) prima del confronto. - Spazi/punteggiatura? "A man, a plan, a canal: Panama". Spesso si richiede di ignorare non-alfanumerici. Pre-processa:
re.sub(r'[^a-z0-9]', '', s.lower())(Python). - Unicode? Emoji, caratteri composti. In Java usa
Character.codePointAtper grapheme cluster corretti. - Complessità spaziale: Approccio 1 crea nuova stringa (O(n) spazio). Approccio 2 è O(1) spazio.
Consiglio per colloqui
Spiega entrambi gli approcci, confronta pro/contro, scrivi codice pulito con nomi variabili chiari, gestisci edge case (stringa vuota, null, lunghezza 1). Testa con esempi.
- Cosa succede se faccio un'offerta su eBay e non la voglio più?
- Effetto "stoffa al vento" con Adobe After Effects (Wave Warp)
Windows 2016
- Cambiare colore punti/serie nei grafici Excel
- Come rimuovere intestazione e piè di pagina da una sola pagina in Word
- Combinare documenti Word senza perdere formattazione: copia/incolla controllato
- Attivare crossfade su Spotify: transizioni fluide tra brani (1-12 secondi)
- Firmare a mano libera un documento Word con lo strumento Scarabocchio
- L'hacking informatico è un crimine? Differenze tra hacking etico e cracking
- Inviare fax da Ubuntu Linux con efax-gtk
- Come inserire caselle di controllo (checkbox) in Microsoft Outlook