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

Другой от Дельфи, который я думаю, немного более строг, чем другой отправленный пример Дельфи. Это может легко превратиться в играющее в гольф соответствие, но я попытался сделать мой читаемым.

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

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

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

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

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

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

Вот является взломанный вместе версией в C#. Я уверен, что этому не нужен regexes, но это действительно работает точно также с вышеупомянутым палиндромом бикини, как это делает с "Человеком, планом, Панама канала!".

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

Это - вся польза, но является там способом добиться большего успеха алгоритмически? Меня когда-то попросили в интервью распознать палиндром в линейное время и постоянное пространство .

я ни о чем не мог думать тогда, и я все еще не могу.

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

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

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

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

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

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

Вот еще две версии Perl, ни одна из которых не использует reverse. Оба используют основной алгоритм сравнения первого символа строки к последнему, затем отбрасывание их и повторение теста, но они используют различные методы достигания отдельных символов (первое очищает их прочь по одному с regex, второе 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/^(.)(.*)(.)$/\2/) {
    return unless $1 eq $3;
  }

  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 Пошаговых (Нажатие MS). Это - два метода, один для разделения небуквенно-цифрового индикатора и другого для проверки на палиндром.

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

Эффективная версия 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;
}

Я еще не видел рекурсии, таким образом, здесь идет...

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

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

Perl:

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

Это игнорирует регистр и разделяет неалфавитно-цифровые символы (это локаль - и unicode-нейтральный).

C++:

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

Perl:

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

Python:

if s == s[::-1]: return True

Java:

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

Я должен был сделать это для проблемы программирования, вот отрывок моего Haskell:

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

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

Scala

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[], метод возвращается после проверки строки, он игнорирует пробелы и <,>, но это можно расширить, чтобы игнорировать больше, возможно, реализовать regex-сопоставление списка игнорирования.

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. A, man a plan a canal,,Panama 3. ABC BA 4. M 5. ACCB

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

OCaml:

let rec palindrome s =
  s = (tailrev s)

источник