Условие
Начинающий программист Алла решила найти работу и отправила резюме в одну очень известную компанию. Собеседование с рекрутером прошло безупречно, и девушку пригласили на следующий этап — техническое интервью с техлидом Степаном.
«Алла, я хочу посмотреть, как вы пишете код, — произнес Степан. — Попробуйте решить простую задачу.
Вы знаете, что ваше имя — палиндром? Оно одинаково читается и с начала, и с конца. Давайте проверим это. Напишите функцию на Python, которая докажет, что ваше имя — палиндром, а мое — нет».
Задача
Помогите Алле с тестовым заданием. Напишите функцию, которая принимает на вход слово и определяет, является ли это палиндромом. Функция должна возвращать True, если является палиндромом, и False в противном случае. Решение должно работать за линейное время.
Пример:
- Ввод: «Alla», Вывод: True;
- Ввод: «Stepan», Вывод: False.
Решение
Задачу можно решить несколькими способами, например, с помощью рекурсии или стека. Но мы рассмотрим другое, более оптимальное решение — с помощью среза сравним исходное слово с его реверсированной версией:
def is_palindrome(s):
s_lower = s.lower()
return s_lower == s_lower[::-1]
Здесь s_lower — это строка (слово), в которой все символы приведены к нижнему регистру с помощью метода lower(). Функция is_palindrome принимает на вход строку s_lower и сравнивает ее с зеркальным отражением s_lower[::-1], чтобы определить, является ли она палиндромом. Если строки равны, функция возвращает True, иначе — False.
print(is_palindrome("Alla")) # True
print(is_palindrome("Stepan")) # False
Почему мы не сравниваем строки посимвольно
Можно было бы сравнивать строки посимвольно — (s_lower[0] == s_lower[-1]) and (s_lower[1] == s_lower[-2]), но наш вариант линейно лучше.
В случае с s_lower == s_lower[::-1] мы сравниваем всю строку s_lower с ее обратным порядком за одну операцию среза. Время выполнения этого решения зависит от длины строки s_lower.
При посимвольном сравнении мы бы проверяли, является ли первый символ равным последнему и второй символ равным предпоследнему. Если оба сравнения истинны, то условие верно, иначе — оно ложно. Время выполнения в этом случае постоянное и не зависит от длины строки s_lower.
Какие факторы влияют на потребление памяти
Использование дополнительных переменных. Если в решении задачи используются дополнительные переменные для хранения зеркального отражения строки или других промежуточных результатов, это может привести к дополнительному потреблению памяти.
Тип данных. В Python строки являются неизменяемыми объектами, и каждая новая строка будет занимать дополнительную память. Если в решении используются дополнительные строки, это может привести к увеличению потребления памяти.
Длина строки. Чем длиннее строка, тем больше памяти будет занимать ее хранение. Создание зеркального отражения s_lower[::-1] требует создания новой строки, которая занимает дополнительную память — примерно в два раза больше, чем исходная строка s. Однако эта дополнительная память освобождается после выполнения сравнения. В данном случае для сравнения строк используется оператор ==, который может потреблять дополнительную память в зависимости от реализации.
