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

Ссылка на leetcode: https://leetcode.com/problems/valid-palindrome/description/

Статья про проверку на палиндром: Проверка на палиндром.

Усложнение задачи проверки на палиндром.

Условие. Проверить, является ли строка палиндромом. Палиндром — это строка, которая читается одинаково слева направо и справа налево. Нужно игнорировать пробелы, регистр букв и все символы, которые не являются английскими буквами и цифрами. Например: “A b a” -> палиндром, “A!23 * 32a”-> палиндром.

Решение. Для решения также будем использовать метод Two Pointers. Первый указатель будет указывать на начало строки, второй на конец строки. Будем итерироваться по строке до тех пока первый индекс меньше второго. На каждой итерации будем делать несколько проверок:

1. Если символ, на который указывает первый указатель, не является буквой или цифрой, то игнорируем его увеличением индекса на единицу и переходим на следующую итерацию цикла.

2. Если символ, на который указывает второй указатель, не является буквой или цифрой, то игнорируем его уменьшением индекса на единицу и переходим на следующую итерацию цикла.

3. Если оба символа являются буквами или цифрами, то приводим их к одному реестру (например нижнему) и сравниваем. Если они не равны, то строка не палиндром. Если равны, то увеличиваем первый индекс и уменьшаем второй.

Time complexity: O(n), Space Complexity O(1).

Реализация:

    class Solution {
        public boolean isPalindrome(String s) {
            int left = 0;
            int right = s.length() - 1;
            while (left < right) {
                if (!isAlphaNum(s.charAt(left))) {
                    left++;
                } else if (!isAlphaNum(s.charAt(right))) {
                    right--;
                } else {
                    if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                        return false;
                    }
                    left++;
                    right--;
                }
            }
            return true;
        }

        //Можно заменить на Character.isLetterOrDigit()
        private boolean isAlphaNum(char c) {
            return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9');
        }
    }