Valid Palindrome

Условие

Дана строка s. Необходимо определить, является ли она палиндромом, игнорируя пробелы, знаки препинания и различие между верхним и нижним регистром.

Примеры

Input: “A man, a plan, a canal: Panama”

Output: true

Explanation: Строка является палиндромом, если игнорировать символы, не являющиеся буквами и цифрами, и регистр.

Input: “race a car”

Output: false

Explanation: Строка не является палиндромом.

Input: ” “

Output: true

Explanation: Пустая строка считается палиндромом.

Решение

fun isPalindrome(s: String): Boolean {
    var left = 0 // Указатель на начало строки
    var right = s.length - 1 // Указатель на конец строки

    while (left < right) {
        // Пропуск неалфавитных и нецифровых символов с начала строки
        while (left < right && !s[left].isLetterOrDigit()) {
            left++
        }
        // Пропуск неалфавитных и нецифровых символов с конца строки
        while (left < right && !s[right].isLetterOrDigit()) {
            right--
        }
        
        // Сравнение символов в нижнем регистре
        if (left < right && s[left].lowercaseChar() != s[right].lowercaseChar()) {
            return false
        }
        
        left++ // Перемещение указателя вправо
        right-- // Перемещение указателя влево
    }

    return true // Если все сравнения прошли успешно, строка является палиндромом
}

Временная сложность

O(n), где n — длина строки, так как требуется пройти по всем символам строки.

Пространственная сложность

O(1), так как дополнительная память не используется для хранения данных.