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

Условие

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

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

• Казак
• А роза упала на лапу Азора
• Do geese see God?
• Madam, I'm Adam

Ограничение по памяти O(1). """

Ответ

Для проверки, является ли строка палиндромом с ограничением по памяти O(1), можно использовать два указателя — один с начала строки, другой с конца, и двигать их навстречу друг другу, сравнивая символы.

При этом нужно игнорировать пробелы, знаки препинания и регистр.

Пример на Go:

import (
    "unicode"
    "strings"
)

func isPalindrome(s string) bool {
    left, right := 0, len(s)-1

    for left < right {
        // Пропускаем не буквенно-цифровые символы слева
        for left < right && !unicode.IsLetter(rune(s[left])) && !unicode.IsDigit(rune(s[left])) {
            left++
        }
        // Пропускаем не буквенно-цифровые символы справа
        for left < right && !unicode.IsLetter(rune(s[right])) && !unicode.IsDigit(rune(s[right])) {
            right--
        }

        if left < right {
            if unicode.ToLower(rune(s[left])) != unicode.ToLower(rune(s[right])) {
                return false
            }
            left++
            right--
        }
    }
    return true
}

// Пример использования:
// fmt.Println(isPalindrome("А роза упала на лапу Азора")) // true

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