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

Давайте потренируемся работать со строками в Python и решим задачку.

 # Напишите функцию, которая будет принимать строку и проверять,
 # является ли она палиндромом или одной из перестановок палиндрома.
 # Палиндром не ограничивается словарными словами.
 # Можно игнорировать регистр и небуквенные символы.

Итак, у нас тут пара непонятных слов, которые интервьюеры любят вставлять в задачки для собеседований. Палиндром, как вы, возможно, знаете, это слово-перевертыш (или строка-перевертыш). Он одинаково читается слева направо и справа налево. Примеры палиндромов — «А роза упала на лапу Азора», «Аргентина манит негра» и т. п. Обратите внимание, что пробелы при чтении игнорируются. То же самое нам разрешается сделать со всеми небуквенными символами в строке.

Перестановка — просто смена мест букв. Если взять палиндром «taco cat» и упорядочить все буквы в алфавитном порядке, получится «aaccott». Это и будет перестановкой палиндрома «tacocat». В нашем решении мы не будем прибегать к сортировке, но это хорошая идея, которую стоит иметь в виду.

Давайте начнем с определения нашего метода. Для практики — попробуйте писать код на белой доске или ручкой на бумаге. Это полезно.

def check_pali(our_string):
    pass

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

def check_pali(our_string):
    our_string = our_string.lower()

Теперь давайте обдумаем наш подход. Что общего у всех палиндромов? Если посмотреть на примеры, такие как «tacocat», «racecar» и «kayak», можно заметить, что все буквы кроме центральной повторяются дважды.

В более длинных палиндромах, таких как «Do geese see God?», некоторые буквы могут появляться не дважды, а большее число раз («е» появляется четырежды). Но все равно только какая-то одна буква может появиться нечетное число раз.

Мы можем подсчитать количество вхождений каждой буквы. Если наша строка — перестановка палиндрома, каждая отдельная буква будет встречаться четное число раз. При этом может быть одна (и только одна) буква, встречающаяся нечетное число раз.

Для подсчета вхождений каждой буквы мы создадим отдельную структуру. Лучше всего для этого подойдет словарь.

Инициализируем словарь counts как пустой словарь.

def check_pali(our_string):
    our_string = our_string.lower()
    counts = {}

Теперь давайте переберем строку в цикле. Создадим цикл for, который пройдется по каждому символу строки.

for letter in our_string:

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

if letter in "abcdefghijklmnopqrstuvwxyz":

Но есть способ получше (и его применение произведет хорошее впечатление на вашего интервьюера). Мы можем использовать метод ord(), который возвращает значение Unicode для заданного символа. Вы можете загуглить значения от «a» до «z» или попробовать вывести их в консоли, введя print(ord('a')) и print(ord('z')). Если ищете в таблице, обращайте внимание на регистр, потому что заглавные буквы идут первыми.

С полученными значениями наше условие будет выглядеть следующим образом:

if ord(letter) >= 97 and ord(letter) <= 122:

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

counts = {}
for letter in our_string:
    if letter in counts.keys():
        counts[letter] += 1
    elif ord(letter) >= 97 and ord(letter) <= 122:
        counts[letter] = 1 

Тут все хорошо. Но если вы хотите упростить код, при создании counts можно воспользоваться встроенным классом Python — defaultdict. В defaultdict, если ключ вызывается впервые, он автоматически инициализируется со значением 0. Это позволит нам просто инкрементировать любое значение, вне зависимости от того, есть уже такой ключ в словаре или нет. Если решите использовать этот метод, не забудьте добавить импорт вверху вашего файла.

from collections import defaultdict

counts = defaultdict(int)
for letter in our_string:
    if ord(letter) >= 97 and ord(letter) <= 122:
        counts[letter] += 1 

Итак, у нас есть словарь с количеством вхождений каждой буквы. Если мы захотим вывести словарь после запуска функции для строки «Taco cat», мы получим что-то вроде этого:

 {'t': 2, 'a': 2, 'c': 2, 'o': 1}

Обратите внимание, что регистр и пробелы проигнорированы.

Далее нам нужно перебрать в цикле все буквы в словаре и проверить, четные ли у них значения (максимум одна буква может иметь нечетное значение). При помощи цикла for в Python можно перебирать ключи словаря, так что назовем переменную letter.

for letter in counts:

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

Создадим переменную middle. При обнаружении буквы с нечетным значением можно сохранять ее в эту переменную. Или можно установить для переменной значение True или False.

Для проверки четности используем оператор деления по модулю, который возвращает остаток от деления. Если значение нечетное, % 2 всегда возвращает 1, а если четное — 0.

Если найдена буква с нечетным значением, а в переменной middle уже есть буква (истинное значение), мы возвращаем False (потому что это будет означать наличие двух букв, входящих в строку нечетное число раз).

Все вместе:

middle = ""
for letter in counts:
    if middle and counts[letter] % 2 == 1:
        return False
    elif counts[letter] % 2 == 1:
        middle = letter

Наконец, нужно вернуть True, если мы перебрали все буквы и выяснили, что все, кроме (максимум) одной имеют четные значения. Предложение return True ставится за пределами цикла for. Вот что должно получиться в итоге:

def check_pali(our_string):
    our_string = our_string.lower()
    counts = defaultdict(int)
    for letter in our_string:
        if ord(letter) >= 97 and ord(letter) <= 122:
            counts[letter] += 1 
    # print(counts)
    middle = ""
    for letter in counts:
        if middle and counts[letter] % 2 == 1:
            return False
        elif counts[letter] % 2 == 1:
            middle = letter
    return True

Если мы испробуем это на палиндроме вроде «Taco cat», метод должен вернуть True, а на фразе типа «не палиндром» — False.

print(check_pali("Taco cat"))
-> True
print(check_pali("Not a palindrome"))
-> False

Вот и все. Учтите, что временная сложность этого решения — O(N), поскольку нам приходится перебирать все буквы.

Бонус: возвращаем возможный палиндром

Это экстра-фича для нашей задачи. Допустим, нам дана строка из букв и нужно не только определить, является ли она одной из перестановок палиндрома, но и выдать, каким может быть палиндром.

По центру нашего палиндрома будет стоять символ из переменной middle. Но что, если он встречается в строке нечетное количество раз, но не единожды? Нужно умножить его на его значение. В Python это легко сделать: a * 3 возвращает aaa.

new_pali = ""
if middle:
    new_pali = middle * counts[middle]

Далее мы переберем в цикле словарь и добавим все буквы по обеим сторонам от центра. Чтобы определить, сколько раз нужно добавить каждую букву с каждой стороны, разделим значение буквы в словаре на два. Деление даст нам число с плавающей точкой. Поэтому, чтобы использовать умножение строк, мы приведем полученное число к типу int.

Добавляя этот код к решению задачи, не забудьте закомментировать строку с возвратом True.

    new_pali = ""
    if middle:
        new_pali = middle * counts[middle]
    for letter in counts:
        if letter != middle:
            new_pali = letter * int(counts[letter] / 2) + new_pali + letter * int(counts[letter] / 2) 
    return new_pali

Для строки «Taco cat» наш код вернет «catotac». Любое слово, введенное дважды, превратится в палиндром. Например, при вводе «word word» вернется «drowword».