Jak sprawdzić, czy łańcuch jest palindromem w Javie i Pythonie

Sprawdzanie, czy dany ciąg znaków jest palindromem, to klasyczne pytanie w rozmowach kwalifikacyjnych. Wymaga podstaw manipulacji łańcuchami oraz pętli, a jednocześnie jest na tyle krótkie, że zmieści się w typowym limicie czasu.

Co to jest palindrom?

Palindrom to słowo lub wyrażenie, które czytane od tyłu brzmi tak samo, jak czytane od przodu. Przykłady: dad, mom. Natomiast father i mother nie są palindromami. Nazwa pochodzi od greckich słów „palin” (ponownie) i „dromos” (droga) i została po raz pierwszy użyta przez Ben Jonsona w XVII wieku.

Rozwiązania

• Najprostsze podejście polega na odwróceniu łańcucha i porównaniu go z oryginałem. Operacja odwracania ma złożoność O(n), więc całe rozwiązanie również O(n).
• Alternatywnie można porównywać znaki od początku i od końca, przerywając w momencie pierwszej niezgodności. Formalnie złożoność to O(n/2), co w notacji dużego O również daje O(n), ale w praktyce pozwala zakończyć działanie szybciej, gdy napotkamy różnicę.

Implementacja w Pythonie

Poniżej przykład funkcji sprawdzającej palindrom w Pythonie:

def is_palindrome(s: str, case_sensitive: bool = False) -> bool:
    if not case_sensitive:
        s = s.lower()
    return s == s[::-1]

Implementacja w Javie

Przykładowa metoda w Javie:

public static boolean isPalindrome(String s, boolean caseSensitive) {
    if (!caseSensitive) {
        s = s.toLowerCase();
    }
    int i = 0, j = s.length() - 1;
    while (i < j) {
        if (s.charAt(i) != s.charAt(j)) {
            return false;
        }
        i++; j--;
    }
    return true;
}

Wskazówka

• Upewnij się, czy rozmówca wymaga rozróżniania wielkości liter. W wersji wrażliwej na wielkość Dad nie jest palindromem, ponieważ D ≠ d.