Действительный палиндром — обычная проблема, с которой сталкиваются на технических собеседованиях, особенно при приеме на работу в таких компаниях, как Spotify. Проблема заключается в том, чтобы определить, является ли данная строка палиндромом или словом, фразой или последовательностью, которая читается так же, как вперед, так и назад. Задача состоит в том, чтобы найти эффективное решение, которое может работать с различными пограничными случаями и различными типами входных данных. В этой статье мы более подробно рассмотрим проблему и рассмотрим возможное решение. Давай начнем!

Проблема

Фраза является палиндромом, если после преобразования всех прописных букв в строчные и удаления всех неалфавитно-цифровых символов она читается одинаково вперед и назад. Буквенно-цифровые символы включают буквы и цифры.

Получив строку s, вернуть true, если это палиндром, илиfalseв противном случае.

Пример 1

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Пример 2

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Пример 3

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Интуиция

Мы будем использовать решение с двумя указателями для решения этой проблемы. Основная идея состоит в том, чтобы оба указателя встретились посередине после проверки строковых символов с обоих концов. Указатели пропускают любые небуквенно-цифровые символы и возвращают false в любой точке, где буквенно-цифровые символы из обоих указателей не совпадают.

lower = 0
upper = len(s)-1

Инициализируйте два указателя, как показано, с нижним указателем в начале строки и верхним указателем в конце строки.

while lower < upper: #1
    while lower < upper and not s[lower].isalnum(): #2
        lower += 1
    while lower < upper and not s[upper].isalnum(): #3
        upper -= 1
    if s[lower].lower() != s[upper].lower(): #4 
        return False
    lower += 1 #5 
    upper -= 1 #5
return True #6

#1: Мы используем цикл while, который повторяется до тех пор, пока нижний указатель меньше верхнего.

# 2: Внутренний цикл while, который выполняет итерацию и увеличивает нижний указатель на единицу, пока нижний указатель меньше верхнего указателя И строковый символ, на который указывает нижний указатель, не является буквенно-цифровым.

#3: То же, что и #2, но для верхнего указателя верхний указатель уменьшается на единицу.

#4: Если символ строки нижнего указателя и символ строки верхнего указателя в нижнем регистре не совпадают, мы вернем false.

# 5: Во внешнем цикле while увеличить нижний указатель и уменьшить верхний указатель на 1

# 6: Возвращайте true после перебора всей строки

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

Полный код

lower = 0
upper = len(s)-1
while lower < upper: 
    while lower < upper and not s[lower].isalnum(): 
        lower += 1
    while lower < upper and not s[upper].isalnum(): 
        upper -= 1
    if s[lower].lower() != s[upper].lower(): 
        return False
    lower += 1 
    upper -= 1 
return True

Заключительные слова

Спасибо, что нашли время прочитать эту статью. Если вы нашли это информативным и полезным, пожалуйста, поддержите меня, подписавшись на мою страницу и похлопав ее. Ваше участие побудит меня продолжать создавать для вас ценный контент.

Чтобы перейти на новый уровень, подумайте о том, чтобы стать участником Medium всего за 5 долларов США в месяц. С моей реферальной ссылкой вы получите доступ к огромному количеству знаний от тысяч писателей и присоединитесь к сообществу лидеров мнений. Улучшите свои навыки чтения и письма уже сегодня.