Valid Palindrome

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

Оба подхода работают за время O(n) , потому что каждый символ просматривается постоянное число раз. Предварительная очистка использует O(n) дополнительной памяти для копии. Версия с двумя указателями использует O(1) дополнительной памяти, поскольку хранит только два индекса.

Q: Как проверить, является ли строка палиндромом, игнорируя неалфавитно-цифровые символы?

Держи по одному указателю на каждом конце строки. Перемещай указатель дальше, пропуская любые символы, которые не являются буквами или цифрами, а когда оба указателя окажутся на буквах или цифрах, сравни их в нижнем регистре. Если все сравниваемые пары совпадают, пока указатели не встретятся, строка является палиндромом.

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

Да. Пустой текст читается одинаково в обоих направлениях, поэтому строка вроде ?!-_ , все символы которой игнорируются, возвращает true . Оба подхода справляются с этим без дополнительного кода: очищенный текст равен своей пустой перевёрнутой версии, а два указателя так и не находят различающуюся пару.

Q: Зачем использовать два указателя вместо обращения строки?

Для разворота нужны очищенная копия и перевёрнутая копия, что требует дополнительной памяти O(n) . Два указателя сравнивают одни и те же пары на месте и могут остановиться при первом несовпадении, часто уже через несколько шагов. На собеседованиях обычно просят написать эту версию в качестве дополнительного задания.

ЛегкоДва указателя

+10

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

Все остальные символы, например ., !, ?, :, ;, - или _, игнорируются. Если в s нет ни букв, ни цифр, ничего не останется, а пустой текст считается палиндромом.

Функция

isPalindrome(s: string) → boolean

sstring: текст для проверки, включая знаки препинания
Возвращаетboolean: истинно, если буквы и цифры в s читаются одинаково в обоих направлениях без учёта регистра

Ограничения

1 ≤ s.length ≤ 5 × 10⁴
s содержит английские буквы, цифры и знаки препинания . ! ? : ; - _, без пробелов.

Примеры

Ввод: s = "Was_it_a_car_or_a_cat_I_saw?"
Вывод: true
Пояснение: Убери подчёркивания и вопросительный знак и переведи заглавные буквы в строчные: получится wasitacaroracatisaw, что читается так же и в обратном направлении.

Ввод: s = "race-a-car"
Вывод: false
Пояснение: Без дефисов текст выглядит так: raceacar. Если читать справа налево, он начинается с raca, а не с race: у e в середине в качестве зеркальной пары стоит a, поэтому ответ — false.

Ввод: s = "Step-on-no-pets!"
Вывод: true
Пояснение: Сохранённый текст — steponnopets. Заглавная S соответствует последней s, потому что регистр не учитывается, а дефисы и ! не играют никакой роли.

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

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

Можешь ли ты определить это, используя дополнительную память O(1), не создавая очищенную копию s?

Подсказки

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

Открыто 0 из 3

Решение

Сама проверка на палиндром знакома: первый оставленный символ должен совпадать с последним, второй — с предпоследним и так далее. Сложность этой версии в том, что сравниваемые символы находятся не на зеркальных индексах s, потому что знаки пунктуации неравномерно распределены по обеим сторонам. Их можно сначала удалить или позволить двум указателям пропускать их, двигаясь навстречу друг другу.

Очисти строку, затем сравни её с перевёрнутой версией

Идея

Сформируй текст, о котором спрашивает задача. Пройдись по s, оставь каждую букву или цифру в нижнем регистре, а всё остальное пропусти. Для Step-on-no-pets! получится steponnopets. Теперь вопрос сводится к обычной проверке на палиндром: равен ли этот текст своему перевёрнутому варианту?

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

Каждый символ считывается один раз для очистки и ещё раз для сравнения, поэтому временная сложность составляет O(n). Очищенная копия и её перевёрнутый вариант требуют O(n) дополнительной памяти — именно эти затраты устраняет следующий подход.

Алгоритм

Создай пустую строку cleaned.
Для каждого символа в s, если это буква или цифра, добавь его в нижнем регистре.
Переверни cleaned.
Верни результат проверки, равна ли cleaned своей перевёрнутой версии.

def isPalindrome(s):
    cleaned = [ch.lower() for ch in s if ch.isalnum()]
    return cleaned == cleaned[::-1]

Два указателя, пропускающих знаки препинания

Идея

Очищенная копия нужна только для того, чтобы можно было сравнить символы, расположенные зеркально. То же сравнение можно выполнить непосредственно для s. Установи left на первый индекс, а right — на последний. На каждом шаге, если left указывает на знак пунктуации, сдвинь его вправо; если right указывает на знак пунктуации, сдвинь его влево. Когда оба указателя указывают на буквы или цифры, сравни их в нижнем регистре. Несовпадение означает false; при совпадении оба указателя сдвигаются навстречу друг другу.

Почему это та же проверка? Указатели всегда останавливаются на следующем сохраняемом символе с каждого конца, поэтому они проходят пары (первый сохраняемый, последний сохраняемый), (второй сохраняемый, предпоследний сохраняемый) и так далее — это в точности те же пары, которые проверяются при сравнении с перевёрнутой строкой. В Abc-dcbX первая пара — A и X, и после одного сравнения результат — false.

На каждом шаге перемещается хотя бы один указатель, и они останавливаются, когда встречаются, поэтому цикл выполняется не более n раз. Кроме двух индексов ничего не сохраняется, поэтому дополнительная память составляет O(1).

Алгоритм

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

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

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

Большинство ошибок возникает из-за символов, которые пропускаются, и регистра букв.

Сравнение s[i] с s[n-1-i] в исходной строке. a-ba становится палиндромом после удаления дефиса, но зеркальным символом для - с индексом 1 в исходной строке является b с индексом 2.
Перемещение обоих указателей, когда только один из них указывает на знак пунктуации. Пропускайте символы по одной стороне за раз, иначе указатели собьются с шага.
Пропуск знаков пунктуации во внутреннем цикле, который проходит дальше другого указателя. Для ?!-_ неограниченный внутренний цикл выходит за конец строки; проверяйте left < right при каждом перемещении.
Считать цифры незначащими символами. 0P — это false: цифра 0 сохраняется и сравнивается, и это не буква p.
Возврат false, если ничего не осталось. Строка, состоящая только из знаков пунктуации, например ., после очистки становится пустой строкой, которая является палиндромом.
Строка, состоящая только из цифр, например 12321, может быть воспринята в PHP и R как число. Сначала преобразуйте её в строку.

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

Какова временная сложность задачи Valid Palindrome?

Оба подхода работают за время O(n), потому что каждый символ просматривается постоянное число раз. Предварительная очистка использует O(n) дополнительной памяти для копии. Версия с двумя указателями использует O(1) дополнительной памяти, поскольку хранит только два индекса.

Как проверить, является ли строка палиндромом, игнорируя неалфавитно-цифровые символы?

Держи по одному указателю на каждом конце строки. Перемещай указатель дальше, пропуская любые символы, которые не являются буквами или цифрами, а когда оба указателя окажутся на буквах или цифрах, сравни их в нижнем регистре. Если все сравниваемые пары совпадают, пока указатели не встретятся, строка является палиндромом.

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

Да. Пустой текст читается одинаково в обоих направлениях, поэтому строка вроде ?!-_, все символы которой игнорируются, возвращает true. Оба подхода справляются с этим без дополнительного кода: очищенный текст равен своей пустой перевёрнутой версии, а два указателя так и не находят различающуюся пару.

Зачем использовать два указателя вместо обращения строки?

Для разворота нужны очищенная копия и перевёрнутая копия, что требует дополнительной памяти O(n). Два указателя сравнивают одни и те же пары на месте и могут остановиться при первом несовпадении, часто уже через несколько шагов. На собеседованиях обычно просят написать эту версию в качестве дополнительного задания.

Python

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

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

Случай 1

Случай 2

Случай 3

Ввод

s = "Was_it_a_car_or_a_cat_I_saw?"

Ожидается

true