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

Подход

Преобразуем строку в нижний регистр, удаляем все не-буквенные символы и пробелы. Затем используем двойной указатель для проверки с обоих концов - если символы совпадают до середины, это палиндром.

Решение

public class StringPalindromeChecker {
    
    /**
     * Метод 1: Двойной указатель с очисткой строки
     */
    public static boolean isPalindrome(String str) {
        if (str == null || str.isEmpty()) {
            return true;
        }
        
        // Преобразуем в нижний регистр и удаляем спецсимволы
        String cleaned = str.toLowerCase()
                           .replaceAll("[^a-z0-9]", "");
        
        if (cleaned.isEmpty()) {
            return true;
        }
        
        int left = 0;
        int right = cleaned.length() - 1;
        
        while (left < right) {
            if (cleaned.charAt(left) != cleaned.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        
        return true;
    }
    
    /**
     * Метод 2: Без регулярных выражений (более эффективен)
     */
    public static boolean isPalindromeNoRegex(String str) {
        if (str == null || str.isEmpty()) {
            return true;
        }
        
        int left = 0;
        int right = str.length() - 1;
        
        while (left < right) {
            char leftChar = str.charAt(left);
            char rightChar = str.charAt(right);
            
            // Пропускаем пробелы и спецсимволы слева
            while (left < right && !isAlphaNumeric(str.charAt(left))) {
                left++;
            }
            
            // Пропускаем пробелы и спецсимволы справа
            while (left < right && !isAlphaNumeric(str.charAt(right))) {
                right--;
            }
            
            // Сравниваем в нижнем регистре
            if (Character.toLowerCase(str.charAt(left)) != Character.toLowerCase(str.charAt(right))) {
                return false;
            }
            
            left++;
            right--;
        }
        
        return true;
    }
    
    /**
     * Вспомогательный метод: проверка буквенно-цифрового символа
     */
    private static boolean isAlphaNumeric(char c) {
        return Character.isLetterOrDigit(c);
    }
    
    /**
     * Метод 3: Используя StringBuilder
     */
    public static boolean isPalindromeWithStringBuilder(String str) {
        if (str == null || str.isEmpty()) {
            return true;
        }
        
        String cleaned = str.toLowerCase()
                           .replaceAll("[^a-z0-9]", "");
        
        String reversed = new StringBuilder(cleaned).reverse().toString();
        return cleaned.equals(reversed);
    }
    
    /**
     * Метод подробной проверки с выводом
     */
    public static void verifyPalindrome(String str) {
        System.out.println("Входная строка: \"" + str + "\"");
        
        String cleaned = str.toLowerCase().replaceAll("[^a-z0-9]", "");
        System.out.println("Очищенная строка: \"" + cleaned + "\"");
        
        boolean result = isPalindrome(str);
        System.out.println("Результат: " + (result ? "ДА, палиндром" : "НЕТ, не палиндром"));
        System.out.println();
    }
    
    public static void main(String[] args) {
        System.out.println("=== Проверка строк на палиндром ===\n");
        
        // Примеры
        verifyPalindrome("madam");
        verifyPalindrome("racecar");
        verifyPalindrome("hello");
        verifyPalindrome("A man a plan a canal Panama");
        verifyPalindrome("Was it a car or a cat I saw?");
        verifyPalindrome("12321");
        verifyPalindrome("race a car");
        
        // Граничные случаи
        System.out.println("Граничные случаи:");
        System.out.println("Пустая строка: " + isPalindrome(""));
        System.out.println("Пробелы: \"   \" -> " + isPalindrome("   "));
        System.out.println("Один символ: \"a\" -> " + isPalindrome("a"));
        System.out.println("Спецсимволы: \"!@#\" -> " + isPalindrome("!@#"));
    }
}

Сложность

• Временная сложность: O(n), где n - длина строки (регулярное выражение O(n), двойной указатель O(n))
• Пространственная сложность: O(n) для очищенной строки (или O(1) если пропускаем спецсимволы на лету)

Примеры и тест-кейсы

1. "madam" -> палиндром
2. "racecar" -> палиндром
3. "A man a plan a canal Panama" -> палиндром (игнорируем пробелы и регистр)
4. "Was it a car or a cat I saw?" -> палиндром
5. "hello" -> не палиндром
6. "race a car" -> не палиндром

Edge cases и типичные ошибки

1. Пустая строка: true (пустая строка - палиндром)
2. Один символ: true
3. Пробелы: игнорируются ("a b a" -> палиндром)
4. Регистр: игнорируется ("Aa" -> палиндром)
5. Спецсимволы: игнорируются ("a!b!a" -> палиндром)
6. Только спецсимволы: true ("!@#" -> true)
7. Цифры и буквы: обе учитываются

Метод без регулярных выражений более эффективен для больших строк.