Как проверить, является ли данная строка палиндром?
Это был один из FAIQ [Часто задаваемый вопрос интервью] некоторое время назад, но в основном с использованием C.
Ищете решения на любых языках.
ОТВЕТЫ
Ответ 1
Пример PHP:
Удаляет любые не буквенно-цифровые символы (пробелы, запятые, восклицательные знаки и т.д.), чтобы допускать полные предложения, как указано выше, а также простые слова.
Ответ 2
Windows XP (может также работать на 2000) или позже BATCH script:
Ответ 3
Язык агностический мета-код, затем.
Ответ 4
С# алгоритм на месте. Любая предварительная обработка, например, нечувствительность к регистру или удаление пробелов и пунктуации, должны выполняться до перехода к этой функции.
Изменить: удалил ненужный » +1 » в условиях цикла и потратил сохраненное сравнение на удаление избыточного сравнения длины. Спасибо комментаторам!
Ответ 5
Ответ 6
Более рубиновая переписывание версии Hal Ruby:
Теперь вы можете вызвать palindrome? для любой строки.
Ответ 7
Ответ 8
Ответ 9
Использование хорошей структуры данных обычно помогает произвести впечатление на профессора:
Нажмите половину символов на стек (длина/2).
Поп и сравните каждую char до первой разблокировки.
Если стек имеет нулевые элементы: палиндром.
* в случае строки с нечетной длиной, выкиньте средний char.
Ответ 10
C в доме. (не уверен, что вы не хотели здесь C)
Это вернет истину для «гоночного автомобиля», «гоночного автомобиля», «гоночного автомобиля», «гоночного автомобиля» и «RaCe cAr». Было бы легко изменить, чтобы включить символы или пробелы, но я считаю, что более полезно считать только буквы (и игнорировать регистр). Это работает для всех палиндромов, которые я нашел в ответах здесь, и я не смог обмануть его в ложные негативы/положительные результаты.
Кроме того, если вам не нравится bool в программе «C», он может, очевидно, возвращать int с возвратом 1 и возвращать 0 для true и false соответственно.
Ответ 11
Вот путь python. Примечание: на самом деле это не «pythonic», но демонстрирует алгоритм.
Ответ 12
Ответ 13
ИЗМЕНИТЬ: из комментариев:
Моя наивная реализация с использованием элегантных итераторов. На самом деле вы, вероятно, и остановитесь, как только ваш передний итератор пропустит половину метки к вашей строке.
Ответ 14
Я вижу здесь много неправильных ответов. Любое правильное решение должно игнорировать пробелы и пунктуации (и любые неалфавитные символы на самом деле) и должно быть нечувствительным к регистру.
Несколько примеров хорошего примера:
«Человек, план, канал, Панама».
Как и некоторые непалиндромы.
Пример решения в С# (примечание: пустые и нулевые строки считаются палиндромами в этой конструкции, если это нежелательно, легко изменить):
Ответ 15
Ответ 16
Здесь мое решение в С#
Ответ 17
Здесь мое решение, не используя strrev. Написан на С#, но он будет работать на любом языке, который имеет функцию длины строки.
Ответ 18
Здесь находится версия Python, которая имеет дело с разными случаями, пунктуацией и пробелами.
Ответ 19
Три версии в Smalltalk, от тупого до правильного.
В Smalltalk = — оператор сравнения:
Сообщение #translateToLowercase возвращает строку как строчную:
И в Smalltalk строки являются частью структуры Collection , вы можете использовать сообщение #select:thenCollect: , поэтому здесь последняя версия:
Ответ 20
Обфускация версии C:
Ответ 21
Gnu Awk
Haskell
Какой-то мозг мертв, делая это в Haskell
Обычный английский
«Just reverse the string and if it is the same as before, it a palindrome»
Ответ 22
Ответ 23
Этот Java-код должен работать внутри метода boolean:
Примечание. Вам нужно только проверить первую половину символов с обратной половиной, иначе вы перекрываете и удваиваете количество проверок, которые необходимо выполнить.
Ответ 24
Другой С++. Оптимизирован для скорости и размера.
Ответ 25
Lisp:
Ответ 26
Обратите внимание, что в приведенных выше С++-решениях были некоторые проблемы.
Одно из решений было неэффективным, поскольку оно передало std::string по копиям, и потому что оно повторялось по всем символам, вместо сравнения только половины символов. Тогда даже при обнаружении строки не был палиндром, он продолжал цикл, ожидая своего конца, прежде чем сообщать «false».
Другой был лучше, с очень маленькой функцией, проблема которой заключалась в том, что он не смог проверить ничего, кроме std::string. В С++ легко распространить алгоритм на целую кучу похожих объектов. Шаблозируя свой std::string на «T», он работал бы как на std::string, std:: wstring, std::vector, так и на std:: deque. Но без существенных изменений из-за использования оператора <, std:: list был вне его области.
Мои собственные решения пытаются показать, что решение С++ не остановится при работе с токовым текущим типом, но будет стремиться работать над тем, что ведет себя одинаково, независимо от типа. Например, я мог бы применить мои тесты палиндрома в std::string, в векторе int или в списке «Anything», если Anything был сопоставим через свой оператор = (строить как типы, так и классы).
Обратите внимание, что шаблон можно даже расширить с помощью необязательного типа, который можно использовать для сравнения данных. Например, если вы хотите сравнить нечувствительным к регистру образом или даже сравнить аналогичные символы (например, è, é, ë, ê и e).
Как и царь Леонидас сказал бы: «Шаблоны? Это С++. «
Итак, в С++ существует по крайней мере 3 основных способа сделать это, каждый из которых ведет к другому:
Решение A: c-подобным образом
Проблема в том, что до С++ 0X мы не можем рассматривать массив символов std::string как смежный, поэтому мы должны «обмануть» и получить свойство c_str(). Поскольку мы используем его только для чтения, это должно быть нормально.
Решение B: более «С++» версия
Теперь мы попытаемся применить одно и то же решение, но к любому контейнеру С++ со случайным доступом к его элементам через operator []. Например, любые std:: basic_string, std::vector, std:: deque и т.д. Оператор [] является постоянным доступом для этих контейнеров, поэтому мы не будем терять чрезмерную скорость.
Решение C: Template powah!
Он будет работать практически с любым неупорядоченным STL-подобным контейнером с двунаправленными итераторами Например, любые std:: basic_string, std::vector, std:: deque, std:: list и т.д. Таким образом, эта функция может применяться ко всем STL-подобным контейнерам со следующими условиями: 1 — T — контейнер с двунаправленным итератором 2 — T указывает на сопоставимый тип (через оператор =)
Ответ 27
Простое решение Java:
Ответ 28
Много способов сделать это. Я думаю, что ключ должен сделать это наиболее эффективным способом (без обхода строки). Я бы сделал это как массив char, который можно легко отменить (используя С#).
Ответ 29
В Ruby, преобразование в нижний регистр и удаление всего не алфавитного:
Но это похоже на обман, не так ли? Нет указателей или чего-то еще! Таким образом, здесь также есть версия C, но без прошивки штриховки и символа:
Хорошо, это было весело — я получаю задание; ^)
Ответ 30
Он игнорирует регистр и полоски не буквенно-цифровых символов (он не зависит от локали и юникода).
Эффективный способ проверки, является ли данная строка палиндромом в C
Я готовился к собеседованию и начал работать с простыми вопросами программирования на Си. Один вопрос, с которым я столкнулся, состоял в том, чтобы проверить, является ли данная строка палиндромом. Я написал код, чтобы определить, является ли заданная пользователем строка палиндромом с помощью указателей. Я хотел бы знать, является ли это эффективным способом с точки зрения времени выполнения или есть какие-то улучшения, которые я мог бы сделать к нему. Также было бы хорошо, если бы кто-нибудь предложил, как удалить другие символы, кроме букв (например, апострофные запятые) при использовании указателя. Я добавил свою функцию ниже. Он принимает указатель на строку в качестве параметра и возвращает целое число.
Проверить строку на палиндром
Палиндром этого слово, фраза, номер или другая последовательность единиц , которые могут быть считаны таким же образом в любом направлении.
Чтобы проверить, является ли слово палиндромом, я получаю массив символов слова и сравниваю символы. Я протестировал, и вроде работает. Однако я хочу знать, правильно ли это или есть что улучшить.
Почему не просто:
Пример:
Вводится «андна».
i1 будет 0, а i2 будет 4.
Первую итерацию цикла мы сравним word[0] и word[4] . Они равны, поэтому мы увеличиваем i1 (теперь 1) и уменьшаем i2 (теперь 3).
Итак, мы затем сравниваем n. Они равны, поэтому мы увеличиваем i1 (теперь 2) и уменьшаем i2 (это 2).
Теперь i1 и i2 равны (они оба 2), поэтому условие для цикла while больше не истинно, поэтому цикл завершается, и мы возвращаем true.
Вы можете проверить, является ли строка палиндромом, сравнив ее с ее обратной стороной:
или для версий Java до 1.5,
РЕДАКТИРОВАТЬ: @FernandoPelliccioni предоставил очень тщательный анализ эффективности (или отсутствия таковой) этого решения как с точки зрения времени, так и пространства. Если вас интересует вычислительная сложность этого и других возможных решений этого вопроса, прочтите его!
Краткая версия, которая не включает (неэффективно) инициализацию группы объектов:
В качестве альтернативы рекурсия .
Для тех, кто ищет более короткое рекурсивное решение, чтобы проверить, удовлетворяет ли данная строка как палиндром:
ИЛИ даже короче , если хотите:
также другое решение:
И вот полное решение для потоковой передачи Java 8 . IntStream предоставляет все индексы сезам строки половину длины и затем Comparision с самого начала и с конца делается.
Я работал над решением вопроса, который был помечен как дубликат этого. Можешь тоже бросить сюда .
В вопросе требовалась одна строка для решения этой проблемы, и я воспринял ее больше как литературный палиндром — поэтому пробелы, знаки препинания и верхний / нижний регистр могут испортить результат.
Вот уродливое решение с небольшим тестовым классом:
Извините, что это немного неприятно, но в другом вопросе указано однострочное.
Сверяя палиндром первой половины строки с остальной, в этом случае предполагается удаление любых пробелов.
Я новичок в java, и я рассматриваю ваш вопрос как попытку улучшить свои знания.
- Если строка не состоит из букв или состоит только из одной буквы, это палиндром.
- В противном случае сравните первую и последнюю буквы строки.
- Если первая и последняя буквы отличаются, значит, строка не является палиндромом.
- В остальном первая и последняя буквы совпадают. Снимите их со строки и определите, является ли оставшаяся строка палиндромом. Возьмите ответ для этой меньшей строки и используйте его как ответ для исходной строки, затем повторите с 1 .
Другой способ — использовать char Array
Примечание: но для меня важно делать это в общем виде . Требования состоят в том, чтобы последовательность была двунаправленной итерацией, а элементы последовательности были сопоставимы с использованием равенства. Я не знаю, как это сделать на Java, но вот версия на C ++, я не знаю лучшего способа сделать это для двунаправленных последовательностей.
Если я RandomAccessIterator: этаж (n / 2) сравнений и этаж (n / 2) * 2 итерации
Если I — BidirectionalIterator: floor (n / 2) сравнения и floor (n / 2) * 2 итерации плюс (3/2) * n итераций, чтобы найти середину (средняя функция)