Как проверить, является ли данная строка палиндромом?
Определение:
Палиндром - это слово, фраза, число или другая последовательность единиц, которая имеет свойство считывать одно и то же в любом направлении.
Как проверить, является ли данная строка палиндромом?
Это был один из FAIQ [Часто задаваемый вопрос интервью] некоторое время назад, но в основном с использованием C.
Поиск решений на любом и всех языках возможен.
69 ответов
Пример PHP:
$string = "A man, a plan, a canal, Panama";
function is_palindrome($string)
{
$a = strtolower(preg_replace("/[^A-Za-z0-9]/","",$string));
return $a==strrev($a);
}
Удаляет все не алфавитно-цифровые символы (пробелы, запятые, восклицательные знаки и т. Д.), Чтобы обеспечить полные предложения, как указано выше, а также простые слова.
Windows XP (может также работать на 2000) или более поздний сценарий BATCH:
@echo off
call :is_palindrome %1
if %ERRORLEVEL% == 0 (
echo %1 is a palindrome
) else (
echo %1 is NOT a palindrome
)
exit /B 0
:is_palindrome
set word=%~1
set reverse=
call :reverse_chars "%word%"
set return=1
if "$%word%" == "$%reverse%" (
set return=0
)
exit /B %return%
:reverse_chars
set chars=%~1
set reverse=%chars:~0,1%%reverse%
set chars=%chars:~1%
if "$%chars%" == "$" (
exit /B 0
) else (
call :reverse_chars "%chars%"
)
exit /B 0
Не зависимый от языка метакод...
rev = StringReverse(originalString)
return ( rev == originalString );
C# на месте алгоритм. Любая предварительная обработка, такая как нечувствительность к регистру или удаление пробелов и пунктуация, должна выполняться перед переходом к этой функции.
boolean IsPalindrome(string s) {
for (int i = 0; i < s.Length / 2; i++)
{
if (s[i] != s[s.Length - 1 - i]) return false;
}
return true;
}
Редактировать: удалены ненужные+1"в состоянии цикла и потратил сохраненное сравнение на удаление избыточного сравнения длины. Спасибо комментаторам!
C#: LINQ
var str = "a b a";
var test = Enumerable.SequenceEqual(str.ToCharArray(),
str.ToCharArray().Reverse());
Более переписанная в стиле Ruby версия Hal's Ruby:
class String
def palindrome?
(test = gsub(/[^A-Za-z]/, '').downcase) == test.reverse
end
end
Теперь вы можете позвонить palindrome? на любой строке.
Неоптимизированный Python:
>>> def is_palindrome(s):
... return s == s[::-1]
Java-решение:
public class QuickTest {
public static void main(String[] args) {
check("AmanaplanacanalPanama".toLowerCase());
check("Hello World".toLowerCase());
}
public static void check(String aString) {
System.out.print(aString + ": ");
char[] chars = aString.toCharArray();
for (int i = 0, j = (chars.length - 1); i < (chars.length / 2); i++, j--) {
if (chars[i] != chars[j]) {
System.out.println("Not a palindrome!");
return;
}
}
System.out.println("Found a palindrome!");
}
}
С в доме. (не уверен, что вам не нужен пример C)
bool IsPalindrome(char *s)
{
int i,d;
int length = strlen(s);
char cf, cb;
for(i=0, d=length-1 ; i < length && d >= 0 ; i++ , d--)
{
while(cf= toupper(s[i]), (cf < 'A' || cf >'Z') && i < length-1)i++;
while(cb= toupper(s[d]), (cb < 'A' || cb >'Z') && d > 0 )d--;
if(cf != cb && cf >= 'A' && cf <= 'Z' && cb >= 'A' && cb <='Z')
return false;
}
return true;
}
Это вернет истину для "гоночного автомобиля", "гоночного автомобиля", "гоночного автомобиля", "гоночного автомобиля" и "RaCe cAr". Было бы легко изменить, чтобы включить символы или пробелы, но я думаю, что более полезно только считать буквы (и игнорировать регистр). Это работает для всех палиндромов, которые я нашел в ответах здесь, и я не смог обмануть его в ложные негативы / позитивы.
Кроме того, если вам не нравится bool в программе "C", он, очевидно, может вернуть int с возвращением 1 и возвращением 0 для true и false соответственно.
Использование хорошей структуры данных обычно помогает произвести впечатление на профессора:
Вставьте половину символов в стопку (длина / 2).
Поп и сравнить каждый символ до первого матча.
Если в стеке нет элементов: палиндром.
* в случае строки с нечетной длиной, выбросьте средний символ.
Вот способ питона. Примечание: это не совсем "питон", но он демонстрирует алгоритм.
def IsPalindromeString(n):
myLen = len(n)
i = 0
while i <= myLen/2:
if n[i] != n[myLen-1-i]:
return False
i += 1
return True
Я вижу много неправильных ответов здесь. Любое правильное решение должно игнорировать пробелы и знаки препинания (и любые не алфавитные символы на самом деле) и должно быть без учета регистра.
Вот несколько хороших примеров:
"Человек, план, канал, Панама".
"Тойота это Тойота".
"А"
""
А также некоторые непалиндромы.
Пример решения в C# (примечание: пустые и нулевые строки считаются палиндромами в этом проекте, если это не желательно, это легко изменить):
public static bool IsPalindrome(string palindromeCandidate)
{
if (string.IsNullOrEmpty(palindromeCandidate))
{
return true;
}
Regex nonAlphaChars = new Regex("[^a-z0-9]");
string alphaOnlyCandidate = nonAlphaChars.Replace(palindromeCandidate.ToLower(), "");
if (string.IsNullOrEmpty(alphaOnlyCandidate))
{
return true;
}
int leftIndex = 0;
int rightIndex = alphaOnlyCandidate.Length - 1;
while (rightIndex > leftIndex)
{
if (alphaOnlyCandidate[leftIndex] != alphaOnlyCandidate[rightIndex])
{
return false;
}
leftIndex++;
rightIndex--;
}
return true;
}
РЕДАКТИРОВАТЬ: из комментариев:
bool palindrome(std::string const& s)
{
return std::equal(s.begin(), s.end(), s.rbegin());
}
C++ путь.
Моя наивная реализация с использованием элегантных итераторов. В действительности, вы, вероятно, проверяли бы и останавливались, как только ваш прямой итератор прошел полпути к вашей строке.
#include <string>
#include <iostream>
using namespace std;
bool palindrome(string foo)
{
string::iterator front;
string::reverse_iterator back;
bool is_palindrome = true;
for(front = foo.begin(), back = foo.rbegin();
is_palindrome && front!= foo.end() && back != foo.rend();
++front, ++back
)
{
if(*front != *back)
is_palindrome = false;
}
return is_palindrome;
}
int main()
{
string a = "hi there", b = "laval";
cout << "String a: \"" << a << "\" is " << ((palindrome(a))? "" : "not ") << "a palindrome." <<endl;
cout << "String b: \"" << b << "\" is " << ((palindrome(b))? "" : "not ") << "a palindrome." <<endl;
}
Delphi
function IsPalindrome(const s: string): boolean;
var
i, j: integer;
begin
Result := false;
j := Length(s);
for i := 1 to Length(s) div 2 do begin
if s[i] <> s[j] then
Exit;
Dec(j);
end;
Result := true;
end;
boolean isPalindrome(String str1) {
//first strip out punctuation and spaces
String stripped = str1.replaceAll("[^a-zA-Z0-9]", "");
return stripped.equalsIgnoreCase((new StringBuilder(stripped)).reverse().toString());
}
Версия Java
Рубин:
class String
def is_palindrome?
letters_only = gsub(/\W/,'').downcase
letters_only == letters_only.reverse
end
end
puts 'abc'.is_palindrome? # => false
puts 'aba'.is_palindrome? # => true
puts "Madam, I'm Adam.".is_palindrome? # => true
Вот версия Python, которая имеет дело с различными случаями, пунктуацией и пробелами.
import string
def is_palindrome(palindrome):
letters = palindrome.translate(string.maketrans("",""),
string.whitespace + string.punctuation).lower()
return letters == letters[::-1]
Изменить: бесстыдно украл из аккуратный ответ Блэр Конрад, чтобы удалить немного неуклюжий обработки списка из моей предыдущей версии.
Запутанная версия C:
int IsPalindrome (char *s)
{
char*a,*b,c=0;
for(a=b=s;a<=b;c=(c?c==1?c=(*a&~32)-65>25u?*++a,1:2:c==2?(*--b&~32)-65<26u?3:2:c==3?(*b-65&~32)-(*a-65&~32)?*(b=s=0,a),4:*++a,1:0:*++b?0:1));
return s!=0;
}
Вот мое решение в C#
static bool isPalindrome(string s)
{
string allowedChars = "abcdefghijklmnopqrstuvwxyz"+
"1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string compareString = String.Empty;
string rev = string.Empty;
for (int i = 0; i <= s.Length - 1; i++)
{
char c = s[i];
if (allowedChars.IndexOf(c) > -1)
{
compareString += c;
}
}
for (int i = compareString.Length - 1; i >= 0; i--)
{
char c = compareString[i];
rev += c;
}
return rev.Equals(compareString,
StringComparison.CurrentCultureIgnoreCase);
}
Три версии в Smalltalk, от самых глупых до правильных.
В Smalltalk, = является оператором сравнения:
isPalindrome: aString
"Dumbest."
^ aString reverse = aString
Сообщение #translateToLowercase возвращает строку в нижнем регистре:
isPalindrome: aString
"Case insensitive"
|lowercase|
lowercase := aString translateToLowercase.
^ lowercase reverse = lowercase
И в Smalltalk, строки являются частью Collection рамки, вы можете использовать сообщение #select:thenCollect:Итак, вот последняя версия:
isPalindrome: aString
"Case insensitive and keeping only alphabetic chars
(blanks & punctuation insensitive)."
|lowercaseLetters|
lowercaseLetters := aString
select: [:char | char isAlphabetic]
thenCollect: [:char | char asLowercase].
^ lowercaseLetters reverse = lowercaseLetters
C++
std::string a = "god";
std::string b = "lol";
std::cout << (std::string(a.rbegin(), a.rend()) == a) << " "
<< (std::string(b.rbegin(), b.rend()) == b);
удар
function ispalin { [ "$( echo -n $1 | tac -rs . )" = "$1" ]; }
echo "$(ispalin god && echo yes || echo no), $(ispalin lol && echo yes || echo no)"
Гну Авк
/* obvious solution */
function ispalin(cand, i) {
for(i=0; i<length(cand)/2; i++)
if(substr(cand, length(cand)-i, 1) != substr(cand, i+1, 1))
return 0;
return 1;
}
/* not so obvious solution. cough cough */
{
orig = $0;
while($0) {
stuff = stuff gensub(/^.*(.)$/, "\\1", 1);
$0 = gensub(/^(.*).$/, "\\1", 1);
}
print (stuff == orig);
}
Haskell
Какой-то умопомрачительный способ сделать это в Хаскеле
ispalin :: [Char] -> Bool
ispalin a = a == (let xi (y:my) = (xi my) ++ [y]; xi [] = [] in \x -> xi x) a
Простой английский
"Just reverse the string and if it is the same as before, it's a palindrome"
Вот мое решение, без использования strrev. Написан на C#, но будет работать на любом языке, который имеет функцию длины строки.
private static bool Pal(string s) {
for (int i = 0; i < s.Length; i++) {
if (s[i] != s[s.Length - 1 - i]) {
return false;
}
}
return true;
}
Еще один C++ один. Оптимизирован по скорости и размеру.
bool is_palindrome(const std::string& candidate) {
for(std::string::const_iterator left = candidate.begin(), right = candidate.end(); left < --right ; ++left)
if (*left != *right)
return false;
return true;
}
Этот код Java должен работать внутри логического метода:
Примечание: вам нужно только проверить первую половину символов с обратной половиной, в противном случае вы перекрываете и удваиваете количество проверок, которые необходимо сделать.
private static boolean doPal(String test) {
for(int i = 0; i < test.length() / 2; i++) {
if(test.charAt(i) != test.charAt(test.length() - 1 - i)) {
return false;
}
}
return true;
}
Простое Java-решение:
public boolean isPalindrome(String testString) {
StringBuffer sb = new StringBuffer(testString);
String reverseString = sb.reverse().toString();
if(testString.equalsIgnoreCase(reverseString)) {
return true;
else {
return false;
}
}
Обратите внимание, что в вышеупомянутых решениях C++ были некоторые проблемы.
Одно из решений было неэффективным, потому что оно передавало std:: string by copy, и потому что оно итерировало по всем символам вместо сравнения только половины символов. Затем, даже когда обнаружение строки не было палиндромом, оно продолжало цикл, ожидая его окончания, прежде чем сообщить о "ложном".
Другая была лучше с очень маленькой функцией, проблема которой состояла в том, что она не могла протестировать ничего, кроме std::string. В C++ легко расширить алгоритм на целую кучу похожих объектов. Шаблонируя его std:: string в "T", он работал бы как с std:: string, std:: wstring, std:: vector, так и с std::deque. Но без существенной модификации из-за использования оператора <, std:: list был вне его области.
Мои собственные решения пытаются показать, что решение C++ не остановится на работе с точным текущим типом, но будет стремиться работать с любым, что ведет себя одинаково, независимо от типа. Например, я мог бы применить свои тесты палиндрома к std:: string, к вектору int или к списку "Anything", если бы Anything был сопоставим с помощью своего оператора = (встроенные типы, а также классы).
Обратите внимание, что шаблон можно даже расширить с помощью дополнительного типа, который можно использовать для сравнения данных. Например, если вы хотите сравнить без учета регистра, или даже сравнить похожие символы (например, é, é, ë, ê и e).
Как сказал бы король Леонидас: "Шаблоны? Это C++!!!"
Итак, в C++ есть как минимум 3 основных способа сделать это, каждый из которых ведет к другому:
Решение A: C-подобным способом
Проблема в том, что до C++0X мы не можем считать массив символов std:: string как непрерывный, поэтому мы должны "обмануть" и получить свойство c_str(). Поскольку мы используем его только для чтения, все должно быть в порядке...
bool isPalindromeA(const std::string & p_strText)
{
if(p_strText.length() < 2) return true ;
const char * pStart = p_strText.c_str() ;
const char * pEnd = pStart + p_strText.length() - 1 ;
for(; pStart < pEnd; ++pStart, --pEnd)
{
if(*pStart != *pEnd)
{
return false ;
}
}
return true ;
}
Решение B: более "C++" версия
Теперь мы попробуем применить то же решение, но к любому контейнеру C++ с произвольным доступом к его элементам через operator []. Например, любой std::basic_string, std::vector, std::deque и т. Д. Operator [] - это постоянный доступ для этих контейнеров, поэтому мы не потеряем чрезмерную скорость.
template <typename T>
bool isPalindromeB(const T & p_aText)
{
if(p_aText.empty()) return true ;
typename T::size_type iStart = 0 ;
typename T::size_type iEnd = p_aText.size() - 1 ;
for(; iStart < iEnd; ++iStart, --iEnd)
{
if(p_aText[iStart] != p_aText[iEnd])
{
return false ;
}
}
return true ;
}
Решение C: Шаблон Powah!
Он будет работать практически с любым неупорядоченным STL-подобным контейнером с двунаправленными итераторами. Например, любой std::basic_string, std::vector, std::deque, std:: list и т. Д. Таким образом, эта функция может быть применена ко всем STL -подобные контейнеры со следующими условиями: 1 - T - это контейнер с двунаправленным итератором 2 - Итератор T указывает на сопоставимый тип (через operator =)
template <typename T>
bool isPalindromeC(const T & p_aText)
{
if(p_aText.empty()) return true ;
typename T::const_iterator pStart = p_aText.begin() ;
typename T::const_iterator pEnd = p_aText.end() ;
--pEnd ;
while(true)
{
if(*pStart != *pEnd)
{
return false ;
}
if((pStart == pEnd) || (++pStart == pEnd))
{
return true ;
}
--pEnd ;
}
}
Python:
if s == s[::-1]: return True
Джава:
if (s.Equals(s.Reverse())) { return true; }
PHP:
if (s == strrev(s)) return true;
Perl:
if (s == reverse(s)) { return true; }
Erlang:
string:equal(S, lists:reverse(S)).
Perl:
sub is_palindrome {
my $s = lc shift; # normalize case
$s =~ s/\W//g; # strip non-word characters
return $s eq reverse $s;
}
Простое решение JavaScript. Запустите фрагмент кода для демонстрации.
function checkPalindrome(line){
reverse_line=line.split("").reverse().join("");
return line==reverse_line;
}
alert("checkPalindrome(radar): "+checkPalindrome("radar"));