Как проверить, является ли данная строка палиндромом?

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

Тогда метакод, не зависящий от языка ...

rev = StringReverse(originalString)
return ( rev == originalString );

Вот мое решение на 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);
}

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;

Неоптимизированный Python:

>>> def is_palindrome(s):
...     return s == s[::-1]

Вот способ питона. Примечание: это не совсем так "питонический", но он демонстрирует алгоритм.

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

Windows XP (также может работать на 2000) или более поздних версиях BATCH script:

@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

C#: LINQ

var str = "a b a";
var test = Enumerable.SequenceEqual(str.ToCharArray(), 
           str.ToCharArray().Reverse());

Есть много способов сделать это. Я думаю, главное - сделать это наиболее эффективным способом (без зацикливания строки). Я бы сделал это как массив символов, который можно легко перевернуть (используя C#).

string mystring = "abracadabra";

char[] str = mystring.ToCharArray();
Array.Reverse(str);
string revstring = new string(str);

if (mystring.equals(revstring))
{
    Console.WriteLine("String is a Palindrome");
}

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" в условии цикла и потратил сохраненное сравнение на удаление избыточного сравнения длины. Спасибо комментаторам!

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

Выложите половину символов в стопку (длина / 2) .
Вытащите и сравните каждый символ до первого несоответствия. Если в стеке ноль элементов: палиндром.
* в случае строки с нечетной длиной выбросить средний символ.

Вот мое решение без использования 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;
}

Этот код 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 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!");
}

}

Пример 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);
}

Удаляет все не буквенно-цифровые символы (пробелы, запятые, восклицательные знаки и т. д.), Чтобы можно было использовать как полные предложения, как указано выше, так и простые слова.

Обновлено: из комментариев:

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, который, на мой взгляд, немного более строгий, чем другой представленный пример Delphi. Это может легко превратиться в матч в гольф, но я попытался сделать свой читабельным.

Edit0: Мне было интересно узнать о характеристиках производительности, поэтому я провел небольшой тест. На своей машине я запускал эту функцию для 60-символьной строки 50 миллионов раз, и это заняло 5 секунд.

function TForm1.IsPalindrome(txt: string): boolean;
var
  i, halfway, len : integer;
begin
  Result := True;
  len := Length(txt);

  {
  special cases:
  an empty string is *never* a palindrome
  a 1-character string is *always* a palindrome
  }
  case len of
    0 : Result := False;
    1 : Result := True;
    else begin
      halfway := Round((len/2) - (1/2));  //if odd, round down to get 1/2way pt

      //scan half of our string, make sure it is mirrored on the other half
      for i := 1 to halfway do begin
        if txt[i] <> txt[len-(i-1)] then begin
          Result := False;
          Break;
        end;  //if we found a non-mirrored character
      end;  //for 1st half of string
    end;  //else not a special case
  end;  //case
end;

И здесь то же самое в C#, за исключением того, что я оставил несколько точек выхода, что мне не нравится.

private bool IsPalindrome(string txt) {
  int len = txt.Length;

  /*
  Special cases:
  An empty string is *never* a palindrome
  A 1-character string is *always* a palindrome
  */    
  switch (len) {
    case 0: return false;
    case 1: return true;
  }  //switch
  int halfway = (len / 2);

  //scan half of our string, make sure it is mirrored on the other half
  for (int i = 0; i < halfway; ++i) {
    if (txt.Substring(i,1) != txt.Substring(len - i - 1,1)) {
      return false;
    }  //if
  }  //for
  return true;
}

C# 3 - возвращает false, как только диаграмма, отсчитываемая с начала, не соответствует своему эквиваленту в конце:

static bool IsPalindrome(this string input)
{
    char[] letters = input.ToUpper().ToCharArray();

    int i = 0;
    while( i < letters.Length / 2 )
        if ( letters[i] != letters[letters.Length - ++i] )
            return false;

    return true;
}

Вот версия Python, в которой используются разные регистры, знаки препинания и пробелы.

import string

def is_palindrome(palindrome):
    letters = palindrome.translate(string.maketrans("",""),
                  string.whitespace + string.punctuation).lower()
    return letters == letters[::-1]

Редактировать: Беззастенчиво украл у Блэр Конрад более аккуратный ответ, чтобы убрать немного корявую обработку списков из моей предыдущей версии.

Три версии 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++. Оптимизирован по скорости и размеру.

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;
}

В Ruby преобразование в нижний регистр и удаление всего не алфавитного:

def isPalindrome( string )
    ( test = string.downcase.gsub( /[^a-z]/, '' ) ) == test.reverse
end

Но это похоже на обман, правда? Никаких указателей или чего-то подобного! Итак, вот версия C, но без строчных букв и удаления символов:

#include <stdio.h>
int isPalindrome( char * string )
{
    char * i = string;
    char * p = string;
    while ( *++i ); while ( i > p && *p++ == *--i );
    return i <= p && *i++ == *--p;
}
int main( int argc, char **argv )
{
    if ( argc != 2 )
    {
        fprintf( stderr, "Usage: %s <word>\n", argv[0] );
        return -1;
    }
    fprintf( stdout, "%s\n", isPalindrome( argv[1] ) ? "yes" : "no" );
    return 0;
}

Что ж, это было весело - я получу работу; ^)

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

Вот несколько хороших примеров тестовых случаев:

«Человек, план, канал, Панама».

«Тойота - это Тойота».

"А"

""

А также некоторые непалиндромы.

Пример решения на 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;
}

Перезапись Рубиновая версия Хэла в стиле Ruby:

class String
  def palindrome?
    (test = gsub(/[^A-Za-z]/, '').downcase) == test.reverse
  end
end

Теперь вы можете вызывать palindrome? по любой строке.

C в доме. (не уверен, что вам здесь не нужен пример 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 для истинного и ложного соответственно.

Perl:

sub is_palindrome($)
{
  $s = lc(shift); # ignore case
  $s =~ s/\W+//g; # consider only letters, digits, and '_'
  $s eq reverse $s;
}

Он игнорирует регистр и удаляет не буквенно-цифровые символы (он нейтрален для локали и юникода).

Используя Java, используя Apache Commons String Utils:

public boolean isPalindrome(String phrase) {
  phrase = phrase.toLowerCase().replaceAll("[^a-z]", "");
  return StringUtils.reverse(phrase).equals(phrase);
}

Если мы ищем числа и простые слова, было дано много правильных ответов.

Однако, если мы ищем то, что мы обычно видим как палиндромы в письменной речи (например, «Собака, паника, в пагоде!»), Правильным ответом будет повторение, начиная с обоих концов предложения, индивидуальный пропуск не буквенно-цифровых символов и возвращает false при обнаружении несоответствий.

i = 0; j = length-1;

while( true ) {
  while( i < j && !is_alphanumeric( str[i] ) ) i++;
  while( i < j && !is_alphanumeric( str[j] ) ) j--;

  if ( i >= j ) return true;

  if ( tolower(string[i]) != tolower(string[j]) ) return false;
  i++; j--;
}

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

Мне пришлось сделать это для задачи программирования, вот фрагмент моего Haskell:

isPalindrome :: String -> Bool
isPalindrome n = (n == reverse n)

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; }

Эрланг:

string:equal(S, lists:reverse(S)).

OCaml:

let rec palindrome s =
  s = (tailrev s)

источник

Лисп:

(defun palindrome(x) (string= x (reverse x)))

boolean IsPalindrome(string s) {
return s = s.Reverse();
}

Perl:

sub is_palindrome {
    my $s = lc shift; # normalize case
    $s =~ s/\W//g;    # strip non-word characters
    return $s eq reverse $s;
}

Обфусцированная версия 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++ были некоторые проблемы.

Одно решение было неэффективным, потому что оно передавало std :: string по копии и потому, что оно перебирало все символы, а не сравнивало только половину символов. Затем, даже когда выяснилось, что строка не является палиндромом, он продолжил цикл, ожидая его конца, прежде чем сообщить «ложь».

Другой был лучше, с очень маленькой функцией, проблема которой заключалась в том, что она не могла проверить ничего, кроме std :: string. В C++ алгоритм легко распространяется на множество похожих объектов. Создав шаблон для своего std :: string в "T", он работал бы как с std :: string, std :: wstring, std :: vector, так и с std :: deque. Но без серьезных изменений из-за использования оператора <список std :: list был вне его области видимости.

Мои собственные решения пытаются показать, что решение C++ не остановится на работе с точным текущим типом, но будет стремиться работать с что-либо, который ведет себя одинаково, независимо от типа. Например, я мог бы применить свои тесты палиндрома к std :: string, к вектору int или к списку «Anything», если Anything был сопоставим через свой operator = (встроенные типы, а также классы).

Обратите внимание, что шаблон может быть даже расширен дополнительным типом, который можно использовать для сравнения данных. Например, если вы хотите сравнить без учета регистра или даже сравнить похожие символы (например, è, é, ë, ê и 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 ;
   }
}

C++:

bool is_palindrome(const string &s)
{
    return equal( s.begin(), s.begin()+s.length()/2, s.rbegin());
}

Здесь нет решения Один, которое учитывает, что палиндром также может быть основан на единицах слов, а не только на единицах символов.

Это означает, что ни одно из приведенных решений не является верным для палиндромов, таких как «Девушка купается в бикини, смотрит на мальчика, видит, как мальчик смотрит на бикини на купающуюся девушку».

Вот взломанная версия на C#. Я уверен, что ему не нужны регулярные выражения, но он работает так же хорошо с вышеуказанным палиндромом бикини, как и с «Человек, план, канал - Панама!».

    static bool IsPalindrome(string text)
    {
        bool isPalindrome = IsCharacterPalindrome(text);
        if (!isPalindrome)
        {
            isPalindrome = IsPhrasePalindrome(text);
        }
        return isPalindrome;
    }

    static bool IsCharacterPalindrome(string text)
    {
        String clean = Regex.Replace(text.ToLower(), "[^A-z0-9]", String.Empty, RegexOptions.Compiled);
        bool isPalindrome = false;
        if (!String.IsNullOrEmpty(clean) && clean.Length > 1)
        {
            isPalindrome = true;
            for (int i = 0, count = clean.Length / 2 + 1; i < count; i++)
            {
                if (clean[i] != clean[clean.Length - 1 - i])
                {
                    isPalindrome = false; break;
                }
            }
        }
        return isPalindrome;
    }

    static bool IsPhrasePalindrome(string text)
    {
        bool isPalindrome = false;
        String clean = Regex.Replace(text.ToLower(), @"[^A-z0-9\s]", " ", RegexOptions.Compiled).Trim();
        String[] words = Regex.Split(clean, @"\s+");
        if (words.Length > 1)
        {
            isPalindrome = true;
            for (int i = 0, count = words.Length / 2 + 1; i < count; i++)
            {
                if (words[i] != words[words.Length - 1 - i])
                {
                    isPalindrome = false; break;
                }
            }
        }
        return isPalindrome;
    }

Я еще не видел рекурсии, так что поехали ...

import re

r = re.compile("[^0-9a-zA-Z]")

def is_pal(s):

    def inner_pal(s):
        if len(s) == 0:
            return True
        elif s[0] == s[-1]:
            return inner_pal(s[1:-1])
        else:
            return False

    r = re.compile("[^0-9a-zA-Z]")
    return inner_pal(r.sub("", s).lower())

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

Тогда я ни о чем не мог думать и до сих пор не могу.

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

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)"

Gnu Awk

/* 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

Какой-то мертвый мозг делает это на 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"

Решения, которые удаляют все символы, которые не попадают между A-Z или a-z, очень ориентированы на английский язык. Буквы с диакритическими знаками, такими как à или é, будут удалены!

Согласно Википедии:

The treatment of diacritics varies. In languages such as Czech and Spanish, letters with diacritics or accents (except tildes) are not given a separate place in the alphabet, and thus preserve the palindrome whether or not the repeated letter has an ornamentation. However, in Swedish and other Nordic languages, A and A with a ring (å) are distinct letters and must be mirrored exactly to be considered a true palindrome.

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

set l = index of left most character in word
set r = index of right most character in word

loop while(l < r)
begin
  if letter at l does not equal letter at r
    word is not palindrome
  else
     increase l and decrease r
end
word is palindrome

Эффективная версия C++:

template< typename Iterator >
bool is_palindrome( Iterator first, Iterator last, std::locale const& loc = std::locale("") )
{
    if ( first == last )
        return true;

    for( --last; first < last; ++first, --last )
    {
        while( ! std::isalnum( *first, loc ) && first < last )
            ++first;
        while( ! std::isalnum( *last, loc ) && first < last )
            --last;
        if ( std::tolower( *first, loc ) != std::tolower( *last, loc ) )
            return false;
    }
    return true;
}

Вот еще две версии Perl, ни одна из которых не использует reverse. Оба используют базовый алгоритм сравнения первого символа строки с последним, затем отбрасывают их и повторяют тест, но они используют разные методы получения отдельных символов (первый снимает их по одному с помощью регулярного выражения, второй split преобразует строку в массив символов).

#!/usr/bin/perl

my @strings = ("A man, a plan, a canal, Panama.", "A Toyota's a Toyota.", 
               "A", "", "As well as some non-palindromes.");

for my $string (@strings) {
  print is_palindrome($string)  ? "'$string' is a palindrome (1)\n"
                                : "'$string' is not a palindrome (1)\n";
  print is_palindrome2($string) ? "'$string' is a palindrome (2)\n"
                                : "'$string' is not a palindrome (2)\n";
} 

sub is_palindrome {
  my $str = lc shift;
  $str =~ tr/a-z//cd;

  while ($str =~ s/^(.)(.*)(.)$//) {
    return unless  eq ;
  }

  return 1;
} 

sub is_palindrome2 {
  my $str = lc shift;
  $str =~ tr/a-z//cd;
  my @chars = split '', $str;

  while (@chars && shift @chars eq pop @chars) {};

  return scalar @chars <= 1;
} 

Простой режим в C#, только с использованием библиотек базовых классов

Обновлено: только что увидел, что кто-то сделал массив.

public bool IsPalindrome(string s)
            {
                if (String.IsNullOrEmpty(s))
                {
                    return false;
                }

                else
                {
                    char[] t = s.ToCharArray();
                    Array.Reverse(t);
                    string u = new string(t);
                    if (s.ToLower() == u.ToLower())
                    {
                        return true;
                    }
                }

                return false;
            }

Вот еще один пример для C#, который я использовал при создании примера серверного элемента управления. Его можно найти в книге ASP.NET 3.5 Step by Step (MS Press). Это два метода: один для удаления не буквенно-цифровых символов, а другой для проверки наличия палиндрома.

protected string StripNonAlphanumerics(string str)
{
    string strStripped = (String)str.Clone();
    if (str != null)
    {
        char[] rgc = strStripped.ToCharArray();
        int i = 0;
        foreach (char c in rgc)
        {
            if (char.IsLetterOrDigit(c))
            {
                i++;
            }
            else
            {
                strStripped = strStripped.Remove(i, 1);
            }
        }
    }
    return strStripped;
}
protected bool CheckForPalindrome()
{
    if (this.Text != null)
    {
        String strControlText = this.Text;
        String strTextToUpper = null;
        strTextToUpper = Text.ToUpper();
        strControlText =
                    this.StripNonAlphanumerics(strTextToUpper);
        char[] rgcReverse = strControlText.ToCharArray();
        Array.Reverse(rgcReverse);
        String strReverse = new string(rgcReverse);
        if (strControlText == strReverse)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    else
    {
        return false;
    }
}

Постоянно-правильное решение указателя C / C++. Минимальные операции в цикле.

int IsPalindrome (const char *str)
{
    const unsigned len = strlen(str);
    const char *end = &str[len-1];
    while (str < end)
        if (*str++ != *end--)
            return 0;
    return 1;
}

Простое решение для 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;
    }
}

Мой 2c. Избегает накладных расходов, связанных с полным переворачиванием струны каждый раз, за ​​счет использования короткого замыкания для возврата, как только будет определена природа струны. Да, вы должны сначала подготовить свою строку, но ИМО, это работа другой функции.

В C#

    /// <summary>
    /// Tests if a string is a palindrome
    /// </summary>
    public static bool IsPalindrome(this String str)
    {
        if (str.Length == 0) return false;
        int index = 0;
        while (index < str.Length / 2)
            if (str[index] != str[str.Length - ++index]) return false;

        return true;
    }

Рубин:

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

Скала

def pal(s:String) = Symbol(s) equals Symbol(s.reverse)

Prolog

palindrome(B, R) :-
palindrome(B, R, []).

palindrome([], R, R).
palindrome([X|B], [X|R], T) :-
palindrome(B, R, [X|T]).

    public bool IsPalindrome(string s)
    {
        string formattedString = s.Replace(" ", string.Empty).ToLower();
        for (int i = 0; i < formattedString.Length / 2; i++)
        {
            if (formattedString[i] != formattedString[formattedString.Length - 1 - i])
                return false;
        }
        return true;
    }

Этот метод подойдет для укуса типа «Это была крыса, которую я видел». Но я считаю, что нам нужно исключить специальный символ с помощью Regex.

Версия C#:

Предполагает, что MyString является char [], метод возвращается после проверки строки, он игнорирует пробел и <,>, но это может быть расширено, чтобы игнорировать больше, возможно, реализует соответствие регулярного выражения списку игнорирования.

public bool IsPalindrome()
            if (MyString.Length == 0)
                return false;

            int len = MyString.Length - 1;

            int first = 0;
            int second = 0;

            for (int i = 0, j = len; i <= len / 2; i++, j--)
            {
                while (i<j && MyString[i] == ' ' || MyString[i] == ',')
                    i++;

                while(j>i && MyString[j] == ' ' || MyString[j] == ',')
                    j--;

                if ((i == len / 2) && (i == j))
                    return true;

                first = MyString[i] >= 97 && MyString[i] <= 122 ? MyString[i] - 32 : MyString[i];
                second = MyString[j] >= 97 && MyString[j] <= 122 ? MyString[j] - 32 : MyString[j];

                if (first != second)
                    return false;
            }

            return true;
  }

Быстрые тестовые случаи

отрицательный 1. ABCDA 2. AB CBAG 3. A # $ BDA 4. NULL / EMPTY

положительный 1. ABCBA 2. План канала, Панама. 3. ABC BA 4. М 5. АККБ

дайте мне знать о любых проблемах / ошибках.

Как насчет этого примера PHP:

function noitcnuf( $returnstrrevverrtsnruter, $functionnoitcnuf) {
    $returnstrrev  = "returnstrrevverrtsnruter";
    $verrtsnruter = $functionnoitcnuf;
    return (strrev ($verrtsnruter) == $functionnoitcnuf) ; 
}

public static boolean isPalindrome( String str ) {
    int count = str.length() ;
    int i, j = count - 1 ;
    for ( i = 0 ; i < count ; i++ ) {
        if ( str.charAt(i) != str.charAt(j) ) return false ;
        if ( i == j ) return true ;
        j-- ;
    }
    return true ;
}

Erlang потрясающий

palindrome(L) -> palindrome(L,[]).

palindrome([],_) -> false;
palindrome([_|[]],[]) -> true;
palindrome([_|L],L) -> true;
palindrome(L,L) -> true;
palindrome([H|T], Acc) -> palindrome(T, [H|Acc]).

Еще нет решения с использованием JavaScript?

function palindrome(s) {
  var l = 0, r = s.length - 1;
  while (l < r) if (s.charAt(left++) !== s.charAt(r--)) return false;
  return true
}

Если вы можете использовать Java API и дополнительное хранилище:

public static final boolean isPalindromeWithAdditionalStorage(String string) {
    String reversed = new StringBuilder(string).reverse().toString();
    return string.equals(reversed);
}

Для Java может потребоваться метод на месте:

public static final boolean isPalindromeInPlace(String string) {
    char[] array = string.toCharArray();
    int length = array.length-1;
    int half = Math.round(array.length/2);
    char a,b;
    for (int i=length; i>=half; i--) {
        a = array[length-i];
        b = array[i];
        if (a != b) return false;
    }
    return true;
}

Регулярный подход:

flag = True // Assume palindrome is true
for i from 0 to n/2 
 { compare element[i] and element[n-i-1] // 0 to n-1
   if not equal set flag = False
   break }
return flag

Существует лучший машинно-оптимизированный метод, который использует XOR, но имеет такую ​​же сложность

Подход XOR:

n = length of string
mid_element = element[n/2 +1]
for i from 0 to n
{ t_xor = element[i] xor element[i+1] }
if n is odd compare mid_element and t_xor
else check t_xor is zero

public class palindrome {
public static void main(String[] args) {
    StringBuffer strBuf1 = new StringBuffer("malayalam");
    StringBuffer strBuf2 = new StringBuffer("malayalam");
    strBuf2.reverse();


    System.out.println(strBuf2);
    System.out.println((strBuf1.toString()).equals(strBuf2.toString()));
    if ((strBuf1.toString()).equals(strBuf2.toString()))
        System.out.println("palindrome");
    else
        System.out.println("not a palindrome");
    }
}   

Без учета регистра, дружественная к const версия на простом языке C, которая игнорирует не буквенно-цифровые символы (например, пробелы / знаки препинания). Таким образом, он фактически передаст классику, такую ​​как «Человек, план, канал, Панама».

int ispalin(const char *b)
{
    const char *e = b;
    while (*++e);
    while (--e >= b)
    {
        if (isalnum(*e))
        {
            while (*b && !isalnum(*b)) ++b;
            if (toupper(*b++) != toupper(*e)) return 0;
        }
    }
    return 1;
}

Интервьюер будет искать логику того, как вы подойдете к этой проблеме: Обратите внимание на следующий код Java:

1. всегда проверять, является ли входная строка нулевой
2. проверьте свои базовые случаи.
3. отформатируйте вашу строку соответствующим образом (удалите все, что не является символом / цифрой
4. Скорее всего, они не хотят видеть, знаете ли вы обратную функцию и сравнение, а скорее можете ли вы ответить на вопрос, используя цикл и индексацию.

5. Быстрый возврат, как только вы узнаете свой ответ и не тратите зря ресурсы.

   public static boolean isPalindrome (String s) {

   if (s == null || s.length() == 0 || s.length() == 1)
       return false;
   
   String ss = s.toLowerCase().replaceAll("/[^a-z]/", "");
   
   for (int i = 0; i < ss.length()/2; i++) 
       if (ss.charAt(i) != ss.charAt(ss.length() - 1 - i))
           return false;
   return true;
   

   }

Java со стеками.

public class StackPalindrome {
    public boolean isPalindrome(String s) throws OverFlowException,EmptyStackException{
        boolean isPal=false;
        String pal = "";
        char letter;
        if (s= = " ")
            return true;
        else{   
            s=s.toLowerCase();
            for(int i=0;i<s.length();i++){

            letter=s.charAt(i);

            char[] alphabet = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
            for(int j=0; j<alphabet.length;j++){
                /*removing punctuations*/
                if ((String.valueOf(letter)).equals(String.valueOf(alphabet[j]))){
                    pal +=letter;
                }

            }

        }
        int len=pal.length();
        char[] palArray=new char[len];
        for(int r=0;r<len;r++){
            palArray[r]=pal.charAt(r);
        }
        ArrayStack palStack=new ArrayStack(len);
        for(int k=0;k<palArray.length;k++){
            palStack.push(palArray[k]);
        }
        for (int i=0;i<len;i++){

            if ((palStack.topAndpop()).equals(palArray[i]))
                isPal=true;
            else 
                isPal=false;
        }
    return isPal;
    }
}
public static void main (String args[]) throws EmptyStackException,OverFlowException{

    StackPalindrome s=new StackPalindrome();
    System.out.println(s.isPalindrome("“Ma,” Jerome raps pot top, “Spare more jam!”"));
}

//Single program for Both String or Integer to check palindrome

//In java with out using string functions like reverse and equals method also and display matching characters also

package com.practice;

import java.util.Scanner;

public class Pallindrome {

        public static void main(String args[]) {
        Scanner sc=new Scanner(System.in);
        int i=0,j=0,k,count=0;
        String input,temp;
        System.out.println("Enter the String or Integer");
        input=sc.nextLine();
        temp=input;
        k=temp.length()-1;
        for(i=0;i<=input.length()-1;i++) {
            if (input.charAt(j)==temp.charAt(k)) {
                count++;
            }
            //For matching characters
            j++;
            k--;
        }
                System.out.println("Matching Characters = "+count);

        if (count==input.length()) {
            System.out.println("It's a pallindrome");
        }
        else {
            System.out.println("It's not a pallindrome");
        }

    }

}

Простое решение JavaScript. Запустите фрагмент кода для демонстрации.

function checkPalindrome(line){
      reverse_line=line.split("").reverse().join("");
      return line==reverse_line;
  }
alert("checkPalindrome(radar): "+checkPalindrome("radar"));

public static boolean isPalindrome(String str) {
    return str.equals(new StringBuilder(str).reverse().toString());
}

для версий Java до 1.5,

public static boolean isPalindrome(String str) {
    return str.equals(new StringBuffer().append(str).reverse().toString());
}

или же

public static boolean istPalindrom(char[] word){
    int i1 = 0;
    int i2 = word.length - 1;
    while (i2 > i1) {
        if (word[i1] != word[i2]) {
            return false;
        }
        ++i1;
        --i2;
    }
    return true;
}

// JavaScript Version.
function isPalindrome(str) { 
  str = str.replace(/[^a-zA-Z]/g, '')
  return str.split('').reverse().join('').toUpperCase() === str.toUpperCase()       
}