Palindrome String

Q: Как проверить, является ли строка палиндромом?

Сравните первый символ с последним, второй — с предпоследним и так далее, двигаясь к середине. Если какая-либо пара различается, строка не является палиндромом. Два индекса, начинающиеся с обоих концов и движущиеся навстречу друг другу, позволяют сделать это за один проход.

Q: Можно ли проверить, является ли строка палиндромом, не используя дополнительную память?

Да. Проверка двумя указателями считывает символы на месте и хранит два индекса, поэтому использует дополнительную память O(1) . Сравнить s с его перевёрнутой копией короче, но при этом создаётся вторая строка из n символов.

Q: Какова временная сложность проверки строки на палиндром?

O(n) для строки длины n . Проверка двумя указателями выполняет не более n / 2 сравнений и останавливается при первом несовпадении, поэтому для coddy требуется одно сравнение.

Q: Является ли один символ палиндромом?

Да, в обоих направлениях оно читается одинаково. В цикле с двумя указателями left и right оба начинают с индекса 0, цикл ни разу не выполняется, и функция возвращает true .

НовичокДва указателя Массивы и строки

+10

Строка является палиндромом, если она читается одинаково слева направо и справа налево, например level. Напиши функцию, которая получает строку s, состоящую из строчных английских букв, и возвращает true, если s — палиндром, и false в противном случае.

Функция

isPalindrome(s: string) → boolean

sstring: строка в нижнем регистре для проверки
Возвращаетboolean: true, когда s читается одинаково в обоих направлениях

Ограничения

1 ≤ s.length ≤ 5 × 10⁴
s содержит только строчные английские буквы (a–z).

Примеры

Ввод: s = "racecar"
Вывод: true
Пояснение: Сравнивайте снаружи внутрь: r с r, a с a, c с c. У средней e нет пары, и она ей не нужна, поэтому ответ — true.

Ввод: s = "abba"
Вывод: true
Пояснение: При чётной длине у каждой буквы есть пара: две буквы a совпадают, и две буквы b совпадают, поэтому ответ — true.

Ввод: s = "coddy"
Вывод: false
Пояснение: Первая буква c и последняя буква y уже различаются, поэтому coddy не является палиндромом, и ответ — false.

Дополнительный вопрос

Как бы вы изменили два указателя, чтобы пропускать пробелы и знаки препинания и не учитывать регистр, чтобы Was it a car or a cat I saw считалось палиндромом?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Палиндром равен своей перевёрнутой версии, поэтому можно построить её и сравнить. Копия не нужна: первый символ должен совпадать с последним, второй — с предпоследним и так далее. Два индекса, движущиеся навстречу друг другу, проверяют эти пары на месте и останавливаются при первом несовпадении.

Сравните строку с её перевёрнутой версией

Идея

Переверни s и сравни: перевёрнутая строка racecar — это racecar, а перевёрнутая строка coddy — это yddoc. Строка читается одинаково в обоих направлениях ровно тогда, когда она равна своей перевёрнутой версии.

Время работы — O(n), но перевёрнутая копия требует дополнительно O(n) памяти: 50 000 символов при n = 5 × 10^4. Кроме того, всегда обрабатывается вся строка: результат для coddy можно определить по первой и последней буквам, но сначала переворачиваются все пять букв.

Алгоритм

Создай строку, обратную s, используя функцию разворота, предусмотренную языком, или цикл от последнего символа к первому.
Сравни перевёрнутую строку с s.
Верни true, если они равны, и false в противном случае.

def isPalindrome(s):
    return s == s[::-1]

Два указателя с обоих концов

Идея

При развороте индекс i переходит в индекс n-1-i, поэтому s равно своей перевёрнутой версии тогда и только тогда, когда s[i] равно s[n-1-i] для каждого i. В этом условии каждая пара встречается дважды, поэтому достаточно проверить левую половину. В racecar пары — это (0, 6), (1, 5) и (2, 4); средней e с индексом 3 не нужна пара.

Первая несовпадающая пара доказывает, что ответ — false, поэтому результат для coddy определяется после одного сравнения. Выполняется не более n / 2 сравнений — время O(n), а для двух индексов требуется O(1) памяти. Сначала R считывает строку как вектор кодов символов, что требует O(n).

Алгоритм

Установите left = 0 и right = n-1.
Пока left < right, сравнивайте s[left] с s[right].
Если они различаются, верните false.
Иначе прибавьте 1 к left, вычтите 1 из right и повторите.
Когда указатели встретятся или пересекутся, каждая пара совпадёт: верните true.

def isPalindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

Ловушки и крайние случаи

Возвращать true, как только совпадёт одна пара. abca проходит проверку внешней пары и не проходит внутреннюю, поэтому true возвращается только после цикла.
Задавать для right значение n вместо n-1, из-за чего происходит чтение за концом (в C — завершающего символа '\0'). В Lua и R индексы идут от 1 до n, поэтому там right действительно начинается со значения n.
Сравнивать строки с помощью == в C. reversed == s сравнивает два указателя и возвращает false для копии; используй strcmp.
Создавать строку в обратном порядке с помощью result = result + ch. На каждом шаге копируется уже созданная строка: около 1.25 × 10^9 копирований символов для 50,000 букв.
Использовать целое число для индексации строки Swift: код не скомпилируется. Перебирай s.utf8 или скопируй символы в массив.

Частые вопросы4

Как проверить, является ли строка палиндромом?

Сравните первый символ с последним, второй — с предпоследним и так далее, двигаясь к середине. Если какая-либо пара различается, строка не является палиндромом. Два индекса, начинающиеся с обоих концов и движущиеся навстречу друг другу, позволяют сделать это за один проход.

Можно ли проверить, является ли строка палиндромом, не используя дополнительную память?

Да. Проверка двумя указателями считывает символы на месте и хранит два индекса, поэтому использует дополнительную память O(1). Сравнить s с его перевёрнутой копией короче, но при этом создаётся вторая строка из n символов.

Какова временная сложность проверки строки на палиндром?

O(n) для строки длины n. Проверка двумя указателями выполняет не более n / 2 сравнений и останавливается при первом несовпадении, поэтому для coddy требуется одно сравнение.

Является ли один символ палиндромом?

Да, в обоих направлениях оно читается одинаково. В цикле с двумя указателями left и right оба начинают с индекса 0, цикл ни разу не выполняется, и функция возвращает true.

def isPalindrome(s):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

s = "racecar"

Ожидаемый вывод

true