Проверка дали низът е палиндром в Java и Python

През годините проверката дали даден низ е палиндром се превърна в класически въпрос за интервю за работа. Той изисква умения за работа със символни низове, сравняване и често използва цикли, но не е обширен, което го прави подходящ за решаване в ограничено време.

Какво е палиндром?

Според synonym.com палиндромът е „дума или израз, който се чете еднакво отляво надясно и отдясно наляво“. С други думи, ако обърнем реда на буквите, получаваме същата последователност. Примери – „дядо“, „мама“; докато „баща“ и „майка“ не са палиндроми. Думата идва от гръцки – palin (отново) и dromos (път). Тя е въведена от английския драматург Бен Джонсън през XVII век.

Решения

• Най‑простият начин е да обърнем низа и да го сравним с оригинала. Този метод има линейна сложност O(n), тъй като обръщането на низа е O(n).
• Алтернативно, можем да сравняваме символите от началото и края едновременно, докато стигнем до средата. Сложността е O(n/2), което също се изразява като O(n) в голямо‑О нотация, но предимството е, че при първо несъответствие можем веднага да върнем false, без да обръщаме целия низ.

Имплементация в Python

Примерен код за проверка дали низът е палиндром в Python:

def e_palindrom(s):
    s = s.lower().replace(" ", "")  # премахваме главни букви и интервали
    return s == s[::-1]

# пример
print(e_palindrom("дядо"))  # True

Имплементация в Java

Примерен код за проверка дали низът е палиндром в Java:

public class Palindrome {
    public static boolean ePalindrome(String s) {
        s = s.toLowerCase().replace(" ", "");
        int left = 0, 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(ePalindrome("мама")); // true
    }
}

Съвет

• Уточнете с интервюиращия дали проверката трябва да бъде чувствителна към регистъра. Ако е чувствителна, низът „Dad“ не е палиндром, защото първият символ е главна буква „D“, а последният – малка „d“.