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

Определение:

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

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

Это было одним из FAIQ [Часто Задаваемый Вопрос Интервью] только что, но это главным образом использующее C.

Поиск решений в любом и всех возможных языках.

56
задан 4 revs, 4 users 100% 18 October 2011 в 09:05
поделиться

54 ответа

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

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

46
ответ дан 4 revs 26 November 2019 в 16:58
поделиться

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

import string

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

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

3
ответ дан 5 revs, 2 users 89% 26 November 2019 в 16:58
поделиться

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

24
ответ дан 6 revs 26 November 2019 в 16:58
поделиться

C#: LINQ

var str = "a b a";
var test = Enumerable.SequenceEqual(str.ToCharArray(), 
           str.ToCharArray().Reverse());
15
ответ дан 2 revs, 2 users 73% 26 November 2019 в 16:58
поделиться

Больше перезаписи стиля Ruby версия Ruby Hal:

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

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

14
ответ дан 2 revs 26 November 2019 в 16:58
поделиться

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

>>> def is_palindrome(s):
...     return s == s[::-1]
11
ответ дан Blair Conrad 26 November 2019 в 16:58
поделиться

Решение для 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!");
}

}

11
ответ дан Jonathan 26 November 2019 в 16:58
поделиться

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 для истины и лжи соответственно.

10
ответ дан 4 revs 26 November 2019 в 16:58
поделиться

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

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

10
ответ дан xanadont 26 November 2019 в 16:58
поделиться
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;
6
ответ дан gabr 26 November 2019 в 16:58
поделиться

Вот является 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
8
ответ дан Baltimark 26 November 2019 в 16:58
поделиться

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

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

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

"Тойота Тойота".

""

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

решение В качестве примера в 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;
}
6
ответ дан 4 revs 26 November 2019 в 16:58
поделиться

РЕДАКТИРОВАНИЕ: из комментариев:

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;

}
6
ответ дан 2 revs, 2 users 87% 26 November 2019 в 16:58
поделиться
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
4
ответ дан 2 revs 26 November 2019 в 16:58
поделиться

Вот мое решение, не используя 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;
}
3
ответ дан swilliams 26 November 2019 в 16:58
поделиться

Вот мое решение в 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);
}
3
ответ дан 3 revs 26 November 2019 в 16:58
поделиться

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

public boolean isPalindrome(String phrase) {
  phrase = phrase.toLowerCase().replaceAll("[^a-z]", "");
  return StringUtils.reverse(phrase).equals(phrase);
}
1
ответ дан 2 revs 26 November 2019 в 16:58
поделиться

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

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

1
ответ дан kranzky 26 November 2019 в 16:58
поделиться

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

rev = StringReverse(originalString)
return ( rev == originalString );
29
ответ дан 2 revs, 2 users 80% 26 November 2019 в 16:58
поделиться

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

Три версии в 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
2
ответ дан 4 revs 26 November 2019 в 16:58
поделиться

Обратите внимание, что в вышеупомянутых решениях для 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 ;
   }
}
<час>
2
ответ дан paercebal 26 November 2019 в 16:58
поделиться

Lisp:

(defun palindrome(x) (string= x (reverse x)))
2
ответ дан Alexander Stolz 26 November 2019 в 16:58
поделиться

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

2
ответ дан 3 revs 26 November 2019 в 16:58
поделиться

Этот код 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;
}
2
ответ дан 5 revs 26 November 2019 в 16:58
поделиться

Запутываемая версия 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;
}
3
ответ дан 2 revs, 2 users 90% 26 November 2019 в 16:58
поделиться

Простое решение для 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;
    }
}
2
ответ дан Ascalonian 26 November 2019 в 16:58
поделиться

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
34
ответ дан 2 revs 26 November 2019 в 16:58
поделиться

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"

3
ответ дан 6 revs 26 November 2019 в 16:58
поделиться

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
3
ответ дан 26 November 2019 в 16:58
поделиться
Другие вопросы по тегам:

Похожие вопросы: