125. Valid Palindrome

Задача

Написать функцию, которая определяет, является ли переданная строка палиндромом (читается слева-направо и справа-налево одинаково)

console.log(isPalindrome("Казак")); // true
console.log(isPalindrome("А роза упала на лапу Азора")); // true
console.log(isPalindrome("123 321")); // true (цифры работают!)
console.log(isPalindrome("Madam, I'm Adam")); // true
console.log(isPalindrome("Привет")); // false

Примеры

Пример 1

Input: s = "A man, a plan, a canal: Panama"
Output: true

Пояснение

“amanaplanacanalpanama” — палиндром.

Пример 2

Input: s = "race a car"
Output: false

Пояснение

“raceacar” — не палиндром.

Пример 3

Input: s = " "
Output: true

Пояснение

После удаления неалфавитно-цифровых символов строка пустая, а пустая строка — палиндром.

Решение

Решение

// Временная сложность: O(n)
// Пространственная сложность: O(1)
 
function isPalindrome(str) {
    let left = 0;
    let right = str.length - 1;
 
    while (left < right) {
        const leftChar = str[left];
        const rightChar = str[right];
 
        // Пропускаем символы слева, если они не являются буквами/цифрами
        if (!isAlphaNumeric(leftChar)) {
            left++;
            continue;
        }
 
        // Пропускаем символы справа, если они не являются буквами/цифрами
        if (!isAlphaNumeric(rightChar)) {
            right--;
            continue;
        }
 
        // Сравниваем символы без учета регистра
        if (leftChar.toLowerCase() !== rightChar.toLowerCase()) {
            return false;
        }
 
        left++;
        right--;
    }
 
    return true;
}
 
// Вспомогательная функция для проверки валидности символа
function isAlphaNumeric(char) {
    // Проверка на цифры (0-9)
    if (char >= '0' && char <= '9') return true;
 
    // Проверка на буквы (работает для латиницы, кириллицы и др.)
    // Если у символа есть верхний и нижний регистр, и они отличаются — это буква.
    // Это трюк, который позволяет не хардкодить диапазоны Unicode или Regex.
    return char.toLowerCase() !== char.toUpperCase();
}

Решение 1 (Two Pointers + char codes)

function isPalindrome(s) {
 
    let left = 0; 
    let right = s.length - 1; 
 
    while (left < right) {
        const leftCode = s.charCodeAt(left); 
        const rightCode = s.charCodeAt(right); 
 
        // Проверка alphanumeric через коды символов
        const isLeftValid = (leftCode >= 48 && leftCode <= 57) ||   // 0-9
                            (leftCode >= 65 && leftCode <= 90) ||    // A-Z
                            (leftCode >= 97 && leftCode <= 122); // a-z
 
        const isRightValid = (rightCode >= 48 && rightCode <= 57) ||
                             (rightCode >= 65 && rightCode <= 90) ||
                             (rightCode >= 97 && rightCode <= 122); 
 
        if (!isLeftValid) {
            left++; 
            continue; 
        }
 
        if (!isRightValid) {
            right--; 
            continue; 
        }
 
        // Сравнение с нормализацией только при необходимости
        let leftChar = leftCode; 
        let rightChar = rightCode; 
 
        // Приведение к lowercase через коды (A-Z -> a-z)
        if (leftCode >= 65 && leftCode <= 90) leftChar += 32; 
        if (rightCode >= 65 && rightCode <= 90) rightChar += 32; 
 
        if (leftChar !== rightChar) {
            return false; 
        }
 
        left++;
        right--;
    }
 
    return true;
 
};