Проверить, является ли строка палиндромом

2. Проверить, является ли строка палиндромом

Условие задачи:
Дана строка.

Необходимо определить, является ли она палиндромом.

При проверке:

регистр символов не учитывается;
пробелы и знаки препинания игнорируются;
учитываются только буквы и цифры.

Код:

String text = "A man, a plan, a canal, Panama!";

Для приведённой строки результат:

true

Спойлеры к решению

Подсказки

💡 Используй два указателя: один в начале строки, второй — в конце.
💡 Если текущий символ не является буквой или цифрой, пропусти его.
💡 Сравнивай символы без учёта регистра.
💡 Если хотя бы одна пара различается, строка не является палиндромом.

Решение

public static boolean isPalindrome(String text) {
    int left = 0;
    int right = text.length() - 1;

    while (left < right) {
        while (left < right
                && !Character.isLetterOrDigit(text.charAt(left))) {
            left++;
        }

        while (left < right
                && !Character.isLetterOrDigit(text.charAt(right))) {
            right--;
        }

        char leftChar = Character.toLowerCase(text.charAt(left));
        char rightChar = Character.toLowerCase(text.charAt(right));

        if (leftChar != rightChar) {
            return false;
        }

        left++;
        right--;
    }

    return true;
}

Пример использования:

public static void main(String[] args) {
    String text = "A man, a plan, a canal, Panama!";

    System.out.println(isPalindrome(text)); // true
}

Алгоритм использует два указателя:

left  → начало строки
right → конец строки

Символы, которые не являются буквами или цифрами, пропускаются:

Character.isLetterOrDigit(...)

Затем симметричные символы сравниваются без учёта регистра:

Character.toLowerCase(text.charAt(left))
        == Character.toLowerCase(text.charAt(right))

Если все пары совпали, строка является палиндромом.

Временная сложность — O(n), дополнительная память — O(1).

Такой вариант не требует создавать очищенную копию строки и работает с буквами и цифрами Unicode, а не только с латиницей.