Verifică dacă un șir este palindrom în Java și Python

În ultimii ani, verificarea dacă un șir este palindrom a devenit o întrebare clasică în interviurile de programare. Această provocare pune în valoare concepte de manipulare și comparare a șirurilor, precum și utilizarea buclelor, și poate fi rezolvată rapid în cadrul limitărilor de timp ale unui interviu.

Ce este un palindrom?

Potrivit synonym.com, un palindrom este „un cuvânt sau o frază care se citește la fel în sensul invers și în sensul normal”. Practic, dacă scrii cuvântul în ordine inversă, rezultatul este exact același cu cel obținut în ordine normală. Exemple simple sunt dad și mom, în timp ce father și mother nu sunt palindromuri. Termenul provine din greaca veche: palin (înapoi) + dromos (cale). A fost popularizat în secolul al XVII-lea de dramaturgul englez Ben Jonson.

Soluții posibile

• Reversarea șirului și comparația: Inversăm șirul complet și îl comparăm cu versiunea originală. Această abordare are complexitatea O(n) (unde n este lungimea șirului), deoarece inversarea are costul liniar.
• Comparație pereche din extrem: Comparăm caracterele de la început și de la sfârșit, avansând spre centru. Dacă găsim o diferență, putem returna imediat false. Această metodă este O(n/2) în practică, dar în termeni de notare Big‑O rămâne O(n). Avantajul major este că ne putem opri la prima neconcordanță, economisind timp pentru șiruri lungi.

Implementare în Python

def is_palindrome(s: str) -> bool:
    # Eliminăm spațiile și facem toate literele mici pentru comparație ne‑sensibilă la caz
    s = s.replace(' ', '').lower()
    return s == s[::-1]

# Exemple de utilizare
print(is_palindrome("dad"))       # True
print(is_palindrome("Dad"))       # False (sensibil la caz)
print(is_palindrome("A man a plan a canal Panama"))  # True (după normalizare)

Implementare în Java

public class PalindromeChecker {
    public static boolean isPalindrome(String s) {
        // Eliminăm spațiile și convertim la litere mici
        s = s.replaceAll("\\s", "").toLowerCase();
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isPalindrome("dad")); // true
        System.out.println(isPalindrome("Dad")); // false
        System.out.println(isPalindrome("A man a plan a canal Panama")); // true
    }
}

Notă utilă pentru interviu

• Întreabă interlocutorul dacă dorești să tratezi cazul diferențelor de majuscule/minuscule. Dacă compararea este case‑sensitive, Dad nu este palindrom, deoarece primul caracter este „D” (majuscule) iar ultimul este „d” (minuscule).