Как проверить палиндром

Задача с собеседования: как найти палиндром

Продолжаем разбирать задачки с сайта 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

Здесь мы использовали другой метод пересборки:

1. X.toString() — переводит число в строку.
2. split(«») — разбивает строку на массив из символов. В кавычках принцип разделения — если бы там была точка, то разделили бы на местах точек. А так как там пустота, то делится вообще по каждому из символов.
3. reverse() — меняет элементы в массиве в обратном порядке.
4. join(«») — добавляет результат к пустой строке, чтобы на выходе получить строку в обратном порядке.

Решение без строк

Тем, кто справился с первой частью, предлагают задачу со звёздочкой — сделать то же самое, но не используя строки, а работая только с числами. Попробуем и мы.

Сделаем в JavaScript функцию, которая будет возвращать true, если в переменной лежит палиндром, и false — если нет. Всё остальное будем писать внутри этой функции:

Теперь обработаем три стандартные ситуации:

1. Если в переменной лежит ноль, то это палиндром.
2. Если переменная меньше ноля, то это не палиндром.
3. Если переменная делится на 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 и не подглядывая в наш код.

Получите ИТ-профессию

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

Алгоритм определения палиндрома

Давайте реализуем алгоритм поиска слов-палиндромов на Java.

Что такое палиндром

Для начала надо определиться, что же такое палиндром? Палиндром – это слово или строка текста, которая читается слева направо и справа налево одинаково. Например, палиндромами являются такие слова как «ага», «дед», «довод», «кабак», «мадам», «шалаш». В более широком смысле число «101» также является палиндромом.

Проверка слова

Давайте сначала рассмотрим более простой алгоритм, который на вход получает одно слово без пробелов. В случае, если данное слово палиндром – возвращаем true.

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

private boolean isWordPalindrome(String word) <
var chars = word.toCharArray();
var left = 0 ; // индекс первого символа
var right = chars.length — 1 ; // индекс последнего символа
while (left < right) < // пока не дошли до середины слова
if (chars[left] != chars[right]) <
return false ;
>
left++;
right—;
>
return true ;
>

Сначала преобразуем с помощью метода toCharArray() исходную строку в массив символов, чтобы можно было обращаться к каждому отдельному символу по его порядковому индексу.

Затем заводим две переменных left и right для хранения левого и правого индекса соответственно.

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

В самом цикле проверяем равенство левого и правого символа. Если они различны – сразу возвращаем false и выходим из метода. Далее левый символ увеличиваем на 1, а правый – уменьшаем на 1.

Если мы дошли до середины строки и ни разу не встретили различий, то возвращаем true.

Проверка фразы

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

• Искать такси
• Лидер бредил
• А роза упала на лапу Азора
• Уж редко рукою окурок держу

Как видите, тут уже встречаются пробелы, которые мы просто должны игнорировать. Также нам нужно сравнивать символы независимо от регистра.

Взяв за основу ранее рассмотренный метод, немного модифицируем его, преобразуя сначала все символы в нижний регистр:

private boolean isTextPalindrome(String text) <
var chars = text.toLowerCase().toCharArray();
var left = 0 ;
var right = chars.length — 1 ;
while (left < right) <
if (chars[left] != chars[right]) <
return false ;
>
// .

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

do <
left++;
> while (left < right && chars[left] == ' ' );

Аналогично правый индекс уменьшаем до тех пор, пока он больше левого и пока правый символ – пробел:

do <
right—;
> while (right > left && chars[right] == ‘ ‘ );

В итоге наш улучшенный метод примет следующий вид:

private boolean isTextPalindrome(String text) <
var chars = text.toLowerCase().toCharArray();
var left = 0 ;
var right = chars.length — 1 ;
while (left < right) <
if (chars[left] != chars[right]) <
return false ;
>

Помимо пробелов во фразах могут встречаться и другие символы. Например, знаки препинания. В таком случае, просто замените явную проверку на пробел на вызов метода Character.isLetterOrDigit().

Реализацию данного алгоритма у вас могут спросить на собеседовании, поэтому его полезно знать.

Проверка палиндрома¶

Интересная задача, которая может быть легко решена с использованием структуры данных “дек” — это классическая задача палиндрома. Палиндромом называют строку, которая одинаково читается справа налево и слева направо. Например, radar, toot или madam. Мы хотим создать алгоритм, принимающий на вход строку символов и проверяющий, является ли она палиндромом.

Для решения данной задачи используем дек в качестве хранилища строковых символов. Мы будем обрабатывать строку слева направо и добавлять каждый её элемент в хвост дека. В этот момент он будет работать очень схоже с обычной очередью. Однако, теперь мы можем использовать дуальную функциональность дека. Его голова будет хранить первый символ строки, а хвост — последний (see рисунок 2).

Поскольку мы способны удалять оба элемента сразу, то можно производить сравнение и продолжать только в случае, если символы совпадают. Если соответствие первого и последнего элементов будет сохраняться, то в конечном итоге мы придём или к отсутствию символов, или останемся с деком размером 1 — в зависимости от того, была ли длина исходной строки чётным или нечётным числом. Но обоих случаях входная последовательность будет палиндромом. Полностью функция проверки представлена в ActiveCode 1.

Палиндром. Проверить, является ли слово, строка, число палиндромом на C++

В данной статье решается задача по реализации программы(кода) на C++ для проверки, является ли слово, строка или число палиндромом. Программа должна просить ввести строку( не важно слово это или число), проверять, является ли она палиндромом и возвращать результат.

Что такое палиндром?

Палиндром — это строка(или число), которое можно прочитать одинаково справа налево, либо слева направо.

К примеру, слово «кот» не является палиндромом, а слово «потоп» является палиндромом. Также и с числами: число 12314 — не палиндром, число 345543 — палиндром.

Поняв это, можно начинать реализовывать алгоритм программы.

Функция проверки слова на палидром в C++

Для определения, является ли строка палиндромом, напишем функцию, которая примет на вход строку(объект string), а на выходе вернет логическое значение(тип данных bool). Строка будет содержать слово или число, которое функция проверит на палиндромность. Выходное значение true будет соответствовать тому, что строка является палиндромом, false будет соответствовать тому, что строка НЕ является палиндромом.

Обратите внимание, что строка — это, по сути своей, обычный одномерый массив.

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

Реализуем это в виде кода.

Для начала необходимо определить, сколько символов в строке, для этого воспользуемся методом length().

int len = word.length();

word — это строка, которую приняла функция. Теперь переменная len хранит значение длины строки.

После чего создадим цикл от 0 до len/2 и будем сравнивать элементы.

for(int i = 0; i < len/2; ++i) < if(word[i] != word[len-i-1]) < return false; >>

Обратите внимание, в цикле есть условие. Если i-ый элемент не равен элементу len-i-1, то сразу возвращается false(То есть не палиндром).

Массивы в C++ нумеруются от 0, поэтому чтобы получить первый элемент строки, нам нужно достать 0-ой элемент из массива, а чтобы последний, то нам нужно достать len-1.

Как работает функция проверки на палиндром

Допустим, у нас слово «мотор», то len будет равна 5.

|м о т о р|

|0 1 2 3 4|

Чтобы получить значение последней буквы, необходимо обратиться к массиву строки с индексом len-1 = 4. А чтобы получить значение первой буквы — обращаемся к элементу 0.

Для наглядности немного визуализируем работу функции:

1.Получаем слово «комок».

3. комок

Сравниваем к и к, они равны, идем дальше.

4. комок

Сравниваем о и о, они равны. Далее цикл останавливается, т.к. запущен до len/2, а это 5/2 = 2. В C++ результатом целочисленного деления является целое число с отброшенной дробной частью.

5. В конце функции возвращается true. Что означает, что слово палиндром.

Если бы во время сравнений букв получилось так, что они НЕ равны, то функция сразу бы завершила работу и вернула значение false. Что означает, что слово не палиндром.

Используем нашу функцию проверки на палиндром в программе на C++

Теперь нашу функцию можно вставить в программу на C++ и использовать. Напишем небольшое приложение, которое просит пользователя ввести слово(или число) в консоль, а после этого сообщает ему, является ли введенное слово палиндромом.

Код нашего приложения — это и есть решение задачи «Проверить, является ли слово палиндромом на C++»

Код программы на C++:

#include #include using namespace std; bool check_polindrom(string word) < int len = word.length(); for(int i = 0; i < len/2; ++i) < if(word[i] != word[len-i-1]) < return false; >> return true; > int main() < string str; cout > str; if(check_polindrom(str)) < cout else < cout return 0; >

Теперь компилируем, запускаем и проверяем.

Проверим словом «palindrom»

palindrom — не палиндром

Программа сообщила, что слово не является палиндромом, а это так и есть на самом деле.

Проверим выдуманным словом палиндромом «potomotop»

Программа сообщила, что введенное слово палиндром. Всё верно.

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

Для вас это может быть интересно:

Раздел: Алгоритмы Программирование Метки: C++, string, алгоритм, код, палиндром, функция

Палиндром. Проверить, является ли слово, строка, число палиндромом на C++ : 3 комментария

1. Роман 25.10.2016 Оооооочень понятно и доходчиво, спасибо большое!