PrepBro
← Назад к вопросам

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

1.3 Junior🔥 181 комментариев
#Коллекции и структуры данных#Язык Swift

Условие

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

Требования:

  • Строка может содержать любые символы, но учитывать нужно только числа и латинские буквы
  • Регистр не важен
  • Решение должно работать за константную память O(1) и линейное время O(n)

Пример:

  • "Madam I'm Adam" → true
  • "race a car" → false
  • "A man, a plan, a canal: Panama" → true

Подсказка: Строки в Swift не имеют индексации по целым числам, так как символы могут иметь разную длину.

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Решение

Подход

Для проверки палиндрома со сложностью O(1) по памяти нужно использовать двухпоинтерный подход (two-pointer technique). Сначала отфильтруем только буквы и цифры, затем сравниваем символы с обоих концов, двигаясь к центру.

Основное решение

func isPalindrome(_ s: String) -> Bool {
    let filtered = s.lowercased()
        .filter { $0.isLetter || $0.isNumber }
    
    let chars = Array(filtered)
    var left = 0
    var right = chars.count - 1
    
    while left < right {
        if chars[left] != chars[right] {
            return false
        }
        left += 1
        right -= 1
    }
    
    return true
}

Оптимизированное решение без массива

Если нужна истинная O(1) память (без создания массива):

func isPalindromeOptimized(_ s: String) -> Bool {
    var left = s.startIndex
    var right = s.index(before: s.endIndex)
    
    while left < right {
        // Двигаем левый указатель, пропуская невалидные символы
        while left < right && !s[left].isLetter && !s[left].isNumber {
            left = s.index(after: left)
        }
        
        // Двигаем правый указатель, пропуская невалидные символы
        while left < right && !s[right].isLetter && !s[right].isNumber {
            right = s.index(before: right)
        }
        
        // Сравниваем символы без учёта регистра
        if s[left].lowercased() != s[right].lowercased() {
            return false
        }
        
        left = s.index(after: left)
        right = s.index(before: right)
    }
    
    return true
}

Тестирование

print(isPalindrome("Madam I'm Adam"))              // true
print(isPalindrome("race a car"))                 // false
print(isPalindrome("A man, a plan, a canal: Panama"))  // true
print(isPalindrome("0P"))                          // false
print(isPalindrome("a."))                         // true

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

Первое решение:

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

Оптимизированное решение:

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

Особенности Swift

  1. Индексация строк: В Swift нет прямой индексации по целому числу, используются Index. Поэтому преобразование в массив часто проще и понятнее.

  2. lowercased() vs lowercased() на Character: Нужно вызывать на Character, иначе сравнение может быть неправильным.

  3. isLetter и isNumber: Встроенные методы Character в Swift, работают с Unicode корректно.

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

Для интервью рекомендую первое решение — оно проще, понятнее и по-прежнему имеет хорошую сложность. Оптимизированное решение можно упомянуть как альтернативу, если нужна истинная O(1) память.

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