* Conoscenza del computer >> sistemi >  >> Windows 2016

Verificare se una stringa è palindroma in Java e Python

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) o s.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.codePointAt per 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.

Windows 2016