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

Решение

1. Простое решение (удаление символов)

<?php

function isPalindrome(string $text): bool {
    // Преобразуем в нижний регистр
    $text = mb_strtolower($text);
    
    // Удаляем все символы кроме букв и цифр
    $text = preg_replace('/[^\p{L}\p{N}]/u', '', $text);
    
    // Сравниваем с развернутой строкой
    return $text === strrev($text);
}

// Примеры
echo isPalindrome("А роза упала на лапу Азора") ? "true" : "false"; // true
echo isPalindrome("level") ? "true" : "false";                     // true
echo isPalindrome("hello") ? "true" : "false";                     // false
echo isPalindrome("Was it a car or a cat I saw") ? "true" : "false"; // true
echo isPalindrome("racecar") ? "true" : "false";                   // true

Анализ сложности:

• Временная сложность: O(n) - проходим по строке 3 раза (strtolower, preg_replace, strrev)
• Пространственная сложность: O(n) - создаём новую строку без спецсимволов

2. Оптимизированное решение (двойной указатель)

<?php

function isPalindromeOptimized(string $text): bool {
    // Нормализуем текст
    $clean = mb_strtolower($text);
    $clean = preg_replace('/[^\p{L}\p{N}]/u', '', $clean);
    
    // Используем два указателя с обоих концов
    $left = 0;
    $right = mb_strlen($clean) - 1;
    
    while ($left < $right) {
        $leftChar = mb_substr($clean, $left, 1);
        $rightChar = mb_substr($clean, $right, 1);
        
        if ($leftChar !== $rightChar) {
            return false; // Ранний выход при несовпадении
        }
        
        $left++;
        $right--;
    }
    
    return true;
}

Анализ сложности:

• Временная сложность: O(n) - проходим ровно половину строки
• Пространственная сложность: O(n) - для хранения очищенной строки
• Преимущество: Может выйти раньше при обнаружении несовпадения (early termination)

3. Решение с минимальной памятью (без создания новой строки)

<?php

function isPalindromeMinMemory(string $text): bool {
    // Массив символов, которые пропускаем
    $skipChars = '/[^\p{L}\p{N}]/u';
    
    // Длина текста
    $len = mb_strlen($text);
    $left = 0;
    $right = $len - 1;
    
    while ($left < $right) {
        // Пропускаем спецсимволы слева
        while ($left < $right && !preg_match('/[\p{L}\p{N}]/u', mb_substr($text, $left, 1))) {
            $left++;
        }
        
        // Пропускаем спецсимволы справа
        while ($left < $right && !preg_match('/[\p{L}\p{N}]/u', mb_substr($text, $right, 1))) {
            $right--;
        }
        
        // Сравниваем символы (игнорируя регистр)
        $leftChar = mb_strtolower(mb_substr($text, $left, 1));
        $rightChar = mb_strtolower(mb_substr($text, $right, 1));
        
        if ($leftChar !== $rightChar) {
            return false;
        }
        
        $left++;
        $right--;
    }
    
    return true;
}

Анализ сложности:

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

4. Решение с использованием встроенных функций

<?php

function isPalindromeBuiltIn(string $text): bool {
    // Убираем пробелы, пунктуацию, приводим к одному регистру
    $clean = mb_strtolower($text);
    $clean = preg_replace('/\s+/', '', $clean); // Убираем пробелы
    $clean = preg_replace('/[^\p{L}\p{N}]/u', '', $clean); // Убираем спецсимволы
    
    return $clean === strrev($clean);
}

// Альтернативный вариант с регулярным выражением
function isPalindromeRegex(string $text): bool {
    $text = mb_strtolower($text);
    $text = preg_replace('/[^\p{L}\p{N}]/u', '', $text);
    return preg_match('/^(.)?(?(1)(?1)|)\1?$/u', $text);
}

5. Рекурсивное решение (не рекомендуется)

<?php

function isPalindromeRecursive(string $text): bool {
    // Очищаем текст
    $clean = mb_strtolower($text);
    $clean = preg_replace('/[^\p{L}\p{N}]/u', '', $clean);
    
    return isPalindromeRecursiveHelper($clean, 0, mb_strlen($clean) - 1);
}

function isPalindromeRecursiveHelper(string $text, int $left, int $right): bool {
    // Базовый случай
    if ($left >= $right) {
        return true;
    }
    
    $leftChar = mb_substr($text, $left, 1);
    $rightChar = mb_substr($text, $right, 1);
    
    if ($leftChar !== $rightChar) {
        return false;
    }
    
    return isPalindromeRecursiveHelper($text, $left + 1, $right - 1);
}

Анализ сложности:

• Временная сложность: O(n)
• Пространственная сложность: O(n) - из-за стека вызовов
• Не рекомендуется для больших строк

6. Юнит тесты

<?php

use PHPUnit\Framework\TestCase;

class PalindromeTest extends TestCase {
    public function test_russian_palindrome(): void {
        $this->assertTrue(isPalindrome("А роза упала на лапу Азора"));
    }

    public function test_simple_palindrome(): void {
        $this->assertTrue(isPalindrome("level"));
        $this->assertTrue(isPalindrome("racecar"));
        $this->assertTrue(isPalindrome("noon"));
    }

    public function test_palindrome_with_spaces(): void {
        $this->assertTrue(isPalindrome("Was it a car or a cat I saw"));
    }

    public function test_not_palindrome(): void {
        $this->assertFalse(isPalindrome("hello"));
        $this->assertFalse(isPalindrome("world"));
    }

    public function test_case_insensitive(): void {
        $this->assertTrue(isPalindrome("RaceCar"));
        $this->assertTrue(isPalindrome("LEVEL"));
    }

    public function test_with_punctuation(): void {
        $this->assertTrue(isPalindrome("A man, a plan, a canal: Panama"));
        $this->assertTrue(isPalindrome("race-car"));
    }

    public function test_empty_string(): void {
        $this->assertTrue(isPalindrome(""));
    }

    public function test_single_character(): void {
        $this->assertTrue(isPalindrome("a"));
    }

    public function test_palindrome_with_numbers(): void {
        $this->assertTrue(isPalindrome("12321"));
        $this->assertTrue(isPalindrome("1a2a1"));
    }
}

7. Сравнение всех подходов

8. Рекомендация

Для собеседования:

// ЛУЧШИЙ ВАРИАНТ - простой и эффективный
function isPalindrome(string $text): bool {
    $text = mb_strtolower($text);
    $text = preg_replace('/[^\p{L}\p{N}]/u', '', $text);
    return $text === strrev($text);
}

Для оптимизации памяти:

// Если нужна минимальная память - двойной указатель
function isPalindromeOptimized(string $text): bool {
    $clean = mb_strtolower($text);
    $clean = preg_replace('/[^\p{L}\p{N}]/u', '', $clean);
    
    $left = 0;
    $right = mb_strlen($clean) - 1;
    
    while ($left < $right) {
        if (mb_substr($clean, $left, 1) !== mb_substr($clean, $right, 1)) {
            return false;
        }
        $left++;
        $right--;
    }
    
    return true;
}

Ключевые точки:

1. Используй mb_* функции для корректной работы с UTF-8
2. Regex /[^\p{L}\p{N}]/u удаляет спецсимволы в любом языке
3. Временная сложность O(n) неизбежна
4. Пространственная сложность от O(1) до O(n) в зависимости от подхода
5. Двойной указатель позволяет выйти раньше при несовпадении