Palindrome String

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

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

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

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

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

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

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

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

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

+10

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

Функция

isPalindrome(s: string) → boolean

sstring: строка в нижнем регистре для проверки
Возвращаетboolean: истинно, когда 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.

+16 скрытых тестов при отправке

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

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

Идея

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

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

Кроме того, каждый раз выполняется вся работа целиком. Результат для coddy можно определить по первой и последней буквам, однако этот подход переворачивает все пять символов, прежде чем их сравнить.

Алгоритм

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

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

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

Идея

При обращении строки символ с индексом i перемещается на индекс n-1-i, поэтому s равна своей перевёрнутой версии тогда и только тогда, когда s[i] равно s[n-1-i] для каждого i. Каждая пара встречается в этом списке дважды, поэтому проверяйте только левую половину. Установите left на индекс 0, а right — на индекс n-1, сравните два символа и переместите оба указателя на один шаг внутрь.

Остановитесь, когда указатели встретятся или пересекутся. В racecar они проверяют пары индексов (0, 6), (1, 5) и (2, 4), а затем встречаются на индексе 3, где находится средняя e, которой не нужна пара. В abba они проверяют (0, 3) и (1, 2), а затем пересекаются. Первая несовпадающая пара доказывает, что ответ — 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 сравнений и останавливается при первом несовпадении, поэтому для строки, у которой первый и последний символы различаются, результат определяется после одного сравнения.

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

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

Python

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

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

s = "racecar"

Ожидается

true