Верно ли, что слово читается одинаково как справа налево, так и слева направо (является палиндромом)
Добрый день. Я решила задачу, но не могу понять, в чём ошибка. Тестирующая система просто не принимает ответ, объяснение ошибки в принципе не предусмотрено(решаю на Сириусе). Сама задача:
Дано слово, состоящее только из заглавных и строчных латинских букв. Проверьте, верно ли, что это слово читается одинаково как справа налево, так и слева направо (то есть является палиндромом), если считать заглавные и строчные буквы неразличающимися. Выведите слово YES, если слово является палиндромом, и слово NO, если не является.
Решение необходимо сдать в виде функции IsPalindrome (S), возвращающей значение типа bool. При решении этой задачи нельзя пользоваться вспомогательными массивами или строками.
Ввод Вывод
Radar YES
YES NO
1 2 3 4 5 6 7 8 9 10 11 12 13
def IsPalindrome(inp): inp = inp.lower() if inp == inp[::-1]: return True else: return False S = input() if IsPalindrome(S): print('YES') else: print('NO')
На палиндромах всё прекрасно работает. Почему система не принимает задачу — непонятно.
Заранее спасибо
Задача о наибольшей подпоследовательности-палиндроме
Например, HELOLEH является подпоследовательностью-палиндромом строки HTEOLFEOLEH.
| Задача: |
| Задача о наибольшей подпоследовательности-палиндроме — это задача о поиске наибольшей подпоследовательности, которую можно получить вычеркиванием некоторых букв из данной последовательности таким образом, что оставшаяся подпоследовательность будет палиндромом. |
Решение
Обозначим данную последовательность через [math]S[/math] , а ее элементы — через [math]S[i], 0 \leqslant i \leqslant n — 1[/math] , где [math]n[/math] — длина строки [math]S[/math] . Будем рассматривать возможные подпоследовательности данной последовательности с [math]i — [/math] го по [math]j — [/math] ый символ включительно, обозначив её как [math]S(i, j)[/math] . Длины максимальных подпалиндромов для данной последовательности будем записывать в двумерный массив [math]L[/math] : [math]L[i][j][/math] — длина максимальной подпоследовательности-палиндрома, который можно получить из последовательности [math]S(i, j)[/math] .
Начнем решать задачу с простых подпоследовательностей. Для последовательности из одного элемента (то есть подпоследовательности вида [math]S(i, i)[/math] ) ответ очевиден — ничего вычеркивать не надо, такая строка будет искомой подпоследовательностью-палиндромом. Для последовательности из двух элементов [math]S(i, i + 1)[/math] возможны два варианта: если элементы равны, то мы имеем подпоследовательность-палиндром, ничего вычеркивать не надо. Если же элементы не равны, то вычеркиваем любой.
Пусть теперь нам дана подпоследовательность [math]S(i, j)[/math] . Если [math]S[i][/math] и [math]S[j][/math] элементы подпоследовательности не совпадают, то один из них нужно вычеркнуть. Тогда у нас останется подпоследовательность [math]S(i, j — 1)[/math] или [math]S(i + 1, j)[/math] — то есть мы сведем задачу к подзадаче: [math]L[i][j] = \max(L[i][j — 1], L[i + 1][j])[/math] . Если же первый и последний элементы равны, то мы можем оставить оба, но необходимо знать решение задачи [math]S(i + 1, j — 1):L[i][j] = L[i + 1][j — 1] + 2[/math] . Таким образом получаем следующее рекуррентное соотношение:
[math] L[i][j] = \begin 1, & i = j\\ 0, & i \gt j\\ L[i + 1][j — 1] + 2, & s[i] = s[j] \\ \max(L[i][j — 1], L[i + 1][j]), & s[i] \neq s[j] \end [/math]
Асимптотика
Каждый элемент массива мы вычисляем [math]1[/math] раз за [math]O(1)[/math] обращаясь к уже вычисленным элементам. Так как размер массива [math]n \times n[/math] , то алгоритм работает за [math]O(n^2)[/math]
Пример
Рассмотрим решение на примере последовательности ABACCBA. Первым делом заполняем диагональ массива единицами, они будут соответствовать подпоследовательностями [math]S(i, i)[/math] из одного элемента. Затем начинаем рассматривать подпоследовательности длины два. Во всех подпоследовательностях, кроме [math]S(3, 4)[/math] , элементы различны, поэтому в соответствующие ячейки запишем [math]1[/math] , а в [math]L[3][4][/math] — [math]2[/math] .
Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали. Для подпоследовательностей длины [math]3[/math] получаются следующие значения: в подпоследовательности ABA первый и последний элемент равны, поэтому [math]L[0][2] = L[1][1] + 2[/math] . В остальных подпоследовательностях первый и последний элементы различны.
BAC: [math]L[1][3] = \max(L[1][2], L[2][3]) = 1[/math]
ACC: [math]L[2][4] = \max(L[2][3], L[3][4]) = 2[/math]
CCB: [math]L[3][5] = \max(L[3][4], L[4][5]) = 2[/math]
CBA: [math]L[4][6] = \max(L[4][5], L[5][6]) = 1[/math]
Продолжая далее аналогичные рассуждения, заполним все ячейки над диагональю и в ячейке [math]L[0][6][/math] получим ответ — [math]6[/math] .
Если же в задаче необходимо вывести не длину, а саму подпоследовательность-палиндром, то дополнительно к массиву длин мы должны построить массив переходов — для каждой ячейки запомнить, какой из случаев был реализован.
Последовательность заполнения массива и массив переходов см. на изображениях ниже.
Псевдокод
Перед вызовом процедуры заполняем [math]L[][][/math] начальными значениями: [math]L[i][j] = 1[/math] если [math]i=j[/math] , [math]L[i][j] = 0[/math] , если [math]i\gt j[/math] , в остальных случаях [math]L[i][j]=-1[/math] . При первом вызове функции в качестве аргументов передаем индексы первого и последнего элементов исходной строки. Например для строки длиной [math] N [/math] вызов функции будет иметь следующий вид: [math] \mathrm
Функция для вычисления длины палиндрома:
- Границы исходной последовательности: [math] \mathtt[/math]
int palSubSeq(left: int, right: int): if L[left][right] == -1 if s[left] == s[right] L[left][right] = palSubSeq(left + 1, right - 1) + 2 else L[left][right] = max(palSubSeq(left + 1, right), palSubSeq(left, right - 1)) return L[left][right]
Процедура для построения искомого палиндрома:
- Границы исходной последовательности: [math] \mathtt[/math]
- Границы искомой подпоследовательности-палиндрома, где правой границей будет длина найденного палиндрома: [math] \mathtt[/math]
// palindrome — массив символов, где в palindrome[i] содержится символ искомой последовательности-палиндрома palChars(left: int, right: int, palLeft: int, palRight: int): while left right if left == right and L[left][right] == 1 palindrome[palLeft++] = S[left++] else if S[left] == S[right] palindrome[palLeft++] = S[left++] palindrome[palRight--] = S[right--] else if L[left + 1][right] L[left][right - 1] left++ else right--
См. также
- Задача о наибольшей общей подпоследовательности
- Задача о наибольшей возрастающей подпоследовательности
- Задача о наибольшей общей палиндромной подпоследовательности
Источники информации
- Википедия — Палиндром
- Wikipedia — Palindrome
- Wikipedia — Longest palindromic subsequence
Является ли строка перестановкой палиндрома?
Давайте потренируемся работать со строками в 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)Теперь давайте заполним наш словарь буквами и их количеством. Житейская мудрость подсказывает, что можно применить еще одно условие. Если вызываемого ключа пока в словаре нет, мы его добавляем со значением 1, а если ключ есть, увеличиваем его значение на единицу. Таким образом мы избежим появления ошибки, когда попытаемся получить значение пока не существующего ключа. Выглядит это так:
counts = <> for letter in our_string: if letter in counts.keys(): counts[letter] += 1 elif ord(letter) >= 97 and ord(letter)Тут все хорошо. Но если вы хотите упростить код, при создании counts можно воспользоваться встроенным классом Python — defaultdict . В defaultdict, если ключ вызывается впервые, он автоматически инициализируется со значением 0. Это позволит нам просто инкрементировать любое значение, вне зависимости от того, есть уже такой ключ в словаре или нет. Если решите использовать этот метод, не забудьте добавить импорт вверху вашего файла.
from collections import defaultdict counts = defaultdict(int) for letter in our_string: if ord(letter) >= 97 and ord(letter)Итак, у нас есть словарь с количеством вхождений каждой буквы. Если мы захотим вывести словарь после запуска функции для строки «Taco cat», мы получим что-то вроде этого:
Обратите внимание, что регистр и пробелы проигнорированы.
Далее нам нужно перебрать в цикле все буквы в словаре и проверить, четные ли у них значения (максимум одна буква может иметь нечетное значение). При помощи цикла 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)Если мы испробуем это на палиндроме вроде «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».
Задача с собеседования: как найти палиндром
Продолжаем разбирать задачки с сайта Leetcode. В прошлый раз было про массив и сумму чисел, теперь тоже необычное.
Условия
В переменной X лежит какое-то целое число
Задача — проверить, является ли это число палиндромом.
Задача со звёздочкой — проверить на наличие палиндрома, не используя строки.
Палиндром — это когда строка или число одинаково читается в прямом и обратном направлении:
121 — это палиндром.
А роза упала на лапу Азора — тоже палиндром (если не считать заглавных букв).
12321 — и это палиндром.
Решение, где используем строки
Самый простой способ проверить, число в переменной палиндром или нет, — преобразовать его в строку, выставить знаки задом наперёд и сравнить с оригиналом. Этим мы сразу решаем проблему отрицательных чисел, когда «−121»превращается в «121−» и сразу становится ясно, что это не палиндром.
Сначала решим это на Python. Тут вообще суть в одной строке:
X = 121 if str(X) == str(X)[::-1]: print("Это палиндром") else: print("Это не палиндром")Здесь мы использовали трюк с переворачиванием строки без её изменения — применили конструкцию [::-1]. Работает это так:
- Первым параметром указывают начало, откуда начинать обработку строки. Раз ничего не указано, то начинаем с первого символа.
- Второй параметр — на каком по счёту символе надо остановиться. Здесь тоже ничего нет, поэтому алгоритм пройдёт до конца строки.
- Последний параметр — шаг и направление обработки. У нас указана минус единица, значит, алгоритм обработает строку справа налево, на каждом шаге считывая по символу.
- В итоге этот код вернёт нам строку, собранную в обратном порядке, при этом с оригинальной строкой ничего не случится — она останется неизменной.
Мы уже делали похожие штуки, когда писали свой генератор новых слов, но там было одно двоеточие, а здесь два.
Теперь решим это же, но на JavaScript:
var X = 121; if (X.toString().split("").reverse().join("") == X.toString()) < console.log("Это палиндром") >else
Здесь мы использовали другой метод пересборки:
- X.toString() — переводит число в строку.
- split("") — разбивает строку на массив из символов. В кавычках принцип разделения — если бы там была точка, то разделили бы на местах точек. А так как там пустота, то делится вообще по каждому из символов.
- reverse() — меняет элементы в массиве в обратном порядке.
- join("") — добавляет результат к пустой строке, чтобы на выходе получить строку в обратном порядке.
Решение без строк
Тем, кто справился с первой частью, предлагают задачу со звёздочкой — сделать то же самое, но не используя строки, а работая только с числами. Попробуем и мы.
Сделаем в JavaScript функцию, которая будет возвращать true, если в переменной лежит палиндром, и false — если нет. Всё остальное будем писать внутри этой функции:
Теперь обработаем три стандартные ситуации:
- Если в переменной лежит ноль, то это палиндром.
- Если переменная меньше ноля, то это не палиндром.
- Если переменная делится на 10 без остатка — это тоже не палиндром.
Запишем это на JavaScript:
function palindrome(x) < // если перед нами ноль — это палиндром if(x == 0) < return true; >// если число меньше нуля или делится на 10 без остатка — это не палиндром if(x < 0 || x%10 == 0)< return false; >>Чтобы проверить, является ли число палиндромом или нет, можно сделать так: отрезаем от числа цифры справа по одной, добавляем их в начало нового числа и постоянно сравниваем новое и старое значение. Если они станут равны — перед нами палиндром. Читайте комментарии, чтобы вникнуть в то, что происходит в коде:
function palindrome(x) < // если перед нами ноль — это палиндром if(x == 0) < return true; >// если число меньше нуля или делится на 10 без остатка — это не палиндром if(x < 0 || x%10 == 0)< return false; >// сюда будем собирать число в обратном порядке temp = 0; // а тут будем хранить промежуточные значения икса preX = x; // пока не дойдём до середины числа — повторяем цикл while (x > temp) < // берём самую правую цифру в числе — это остаток от деления на 10 pop = x%10; // запоминаем старое значение переменной X preX = x; // и отрезаем от переменной последнюю цифру — делаем это через целую часть деления на 10 x /= 10; // добавляем отрезанную цифру к обратной переменной temp = temp*10 + pop; >// если обратная переменная совпала с оставшейся половиной исходной переменной — это палиндром // мы добавляем сравнение с предыдущей версией исходной половины (которая на 1 цифру больше) на тот случай, если исходное число состояло из нечётного количества символов и его нельзя было бы разбить строго пополам if(x == temp || preX == temp) return true; // else return false; >;Для запуска кода просто вызываем функцию и передаём её нашу переменную:
// запускаем код
var X = 121;
console.log(palindrome(X));
Чтобы попрактиковаться, попробуйте сделать такое же, но на Python и не подглядывая в наш код.
Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.