Как проверить, является ли данная строка палиндромом? [закрытый]

образец 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);
}

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

Вот версия Python, которая имеет дело с различными случаями, пунктуацией и пробелом.

import string

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

Редактирование: Бесстыдно украл от Blair Conrad более опрятный ответ для удаления немного неуклюжей обработки списков из моей предыдущей версии.

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 версия Ruby Hal:

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 в доме. (не уверенный, если Вы не хотели примера 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;
}

, Который возвратит true для "гоночного автомобиля", "Гоночного автомобиля", "гоночного автомобиля", "гоночного автомобиля" и "Гоночного автомобиля". Было бы легко изменить для включения символов или пробелов также, но я полагаю, что более полезно только считать буквы (и игнорировать регистр). Это работает на все палиндромы, которые я нашел в ответах здесь, и я был неспособен обмануть его в ложные отрицательные стороны/положительные стороны.

кроме того, если Вам не нравится bool в "C" программе, он мог бы, очевидно, возвратить интервал, с возвратом 1 и возвратиться 0 для истины и лжи соответственно.

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

Нажатие половина символов на стек (Длина / 2).
Pop и сравнивают каждый символ до первого несоответствия.
, Если стек имеет нулевые элементы: палиндром.
*в случае строки с нечетной Длиной, выведите средний символ.

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 путем.Примечание: это не действительно, что "pythonic", но это демонстрирует алгоритм.

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;

}

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

версия

Вот мое решение, не используя 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#

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

Используя Java, с помощью Apache палата общин Строка Utils:

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

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

ну, который был забавой - делают я получаю задание; ^)

Агностик языка метакодирует тогда...

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

Много способов сделать это. Я предполагаю, что ключ должен сделать это самым эффективным возможным способом (без цикличного выполнения строка). Я сделал бы это как массив символов, который может быть инвертирован легко (использующий 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");
}

Три версии в 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++, были некоторые проблемы.

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

другой было лучше, с очень небольшой функцией, проблема которой состояла в том, что она не смогла протестировать что-либо еще, чем станд.:: строка. В C++ легко расширить алгоритм до целого набора подобных объектов. Путем шаблонной обработки его станд.:: строка в "T", это работало бы над обоими станд.:: строка, станд.:: wstring, станд.:: вектор и станд.:: двухсторонняя очередь. Но без основной модификации из-за использования оператора < станд.:: список был вне его объема.

Мои собственные решения пытаются показать, что решение для C++ не остановится при работе над точным текущим типом, но будет стремиться работать что-либо , который ведет себя тот же путь, неважно, тип. Например, я мог применить свои тесты палиндрома на станд.:: строка, на векторе интервала или в списке "Чего-либо", пока Что-либо было сопоставимо через его оператор = (сборка в типах, а также классы).

Примечание, что шаблон может даже быть расширен с помощью дополнительного типа, который может использоваться для сравнения данных. Например, если Вы хотите выдержать сравнение нечувствительным к регистру способом, или даже сравнить подобные символы (как ГЁ, Г©, Г «, ГЄ и e).

Как король Leonidas сказал бы: "Шаблоны? Это - C++!!!"

Так, в C++, существует по крайней мере 3 главных способа сделать это, каждый ведущий к другому:

Решение A: подобным c способом

проблема состоит в том, что до C++ 0X, мы не можем рассмотреть станд.:: массив строк символов как непрерывные, таким образом, мы должны "обмануть" и получить 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++ с произвольным доступом к его объектам через оператор []. Например, любой станд.:: basic_string, станд.:: вектор, станд.:: двухсторонняя очередь, и т.д. Оператор [] является постоянным доступом для тех контейнеров, таким образом, мы не потеряем неуместную скорость.

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 контейнером с двунаправленными итераторами, Например, любым станд.:: basic_string, станд.:: вектор, станд.:: двухсторонняя очередь, станд.:: список, и т.д. Так, эта функция может быть применена на все подобные STL контейнеры со следующими условиями: 1 - T является контейнером с двунаправленным итератором 2 - итератор T указывает на сопоставимый тип (через оператор =)

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

Lisp:

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

Другой 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;
}

Запутываемая версия 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;
}

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

Windows XP (мог бы также работать над 2000), или более поздний Сценарий пакетной обработки:

@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++

std::string a = "god";
std::string b = "lol";

std::cout << (std::string(a.rbegin(), a.rend()) == a) << " " 
          << (std::string(b.rbegin(), b.rend()) == b);

Bash

function ispalin { [ "$( echo -n $1 | tac -rs . )" = "$1" ]; }
echo "$(ispalin god && echo yes || echo no), $(ispalin lol && echo yes || echo no)"

Гну 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"

Ruby:

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