Как проверить, что строка является палиндром с использованием регулярных выражений?

Это был вопрос интервью, на который я не мог ответить:

p.s. Уже существует вопрос "Как проверить, является ли данная строка палиндромом?", и он дает много ответов на разных языках, но не отвечает, что использует регулярные выражения.

Ответы

Ответ 1

Ответ на этот вопрос заключается в том, что "это невозможно". Более конкретно, интервьюер задается вопросом, обратили ли вы внимание на свой класс вычислительной теории.

В вашем классе вычислительной теории вы узнали о конечных автоматах. Конечный автомат состоит из узлов и ребер. Каждое ребро аннотируется буквой из конечного алфавита. Один или несколько узлов являются специальными "принимающими" узлами, а один node является "стартом" node. Поскольку каждая буква считывается из данного слова, мы проходим данное ребро в машине. Если мы закончим в принимающем состоянии, тогда мы скажем, что машина "принимает" это слово.

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

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

a ^ x b a ^ x (например, aba, aabaa, aaabaaa, aaaabaaaa,....)

где a ^ x - повторяющееся x раз. Для этого требуется, по крайней мере, x узлов, потому что, увидев "b", мы должны отсчитать x раз, чтобы убедиться, что это палиндром.

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

Ответ 2

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

Я не думаю, что "Это невозможно" - это то, что ищет интервьюер.

$a = "teststring";
while(length $a > 1)
{
   $a =~ /(.)(.*)(.)/;
   die "Not a palindrome: $a" unless $1 eq $3;
   $a = $2;
}
print "Palindrome";

Ответ 3

Это невозможно. Палиндромы не определяются обычным языком. (См., Я узнал что-то в вычислительной теории)

Ответ 4

С регулярным выражением Perl:

/^((.)(?1)\2|.?)$/

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

Ответ 5

Вот, чтобы обнаружить 4-буквенные палиндромы (например: документ) для любого типа символов:

\(.\)\(.\)\2\1

Вот, чтобы обнаружить 5-буквенные палиндромы (например: радар), проверяя только буквы:

\([a-z]\)\([a-z]\)[a-z]\2\1

Итак, нам кажется, что для каждой возможной длины слова требуется другое регулярное выражение. Этот пост в списке рассылки Python содержит некоторые сведения о том, почему (конечные автоматы Automation и откачанная лемма).

Ответ 6

Да, вы можете сделать это в .Net!

(?<N>.)+.?(?<-N>\k<N>)+(?(N)(?!))

Вы можете проверить это здесь! Это замечательный пост!

Ответ 7

В зависимости от того, насколько вы уверены, я бы дал следующий ответ:

Я бы не стал с регулярным выражение. Это не подходит использование регулярных выражений.

Ответ 8

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

(.?)(.?)(.?)(.?)(.?).?\5\4\3\2\1

Ответ 9

StackOverflow полна ответов, таких как "Регулярные выражения? nope, они не поддерживают его. Они не могут его поддерживать".

Истина заключается в том, что регулярные выражения больше не имеют отношения к регулярным грамматикам. Современные функции регулярных выражений, такие как группы рекурсии и балансировки, и доступность их реализаций постоянно растут (см. примеры Ruby здесь, например). На мой взгляд, висит на прежнем убеждении, что регулярные выражения в нашей области не что иное, как концепция программирования, просто контрпродуктивны. Вместо того, чтобы ненавидеть их за выбор слова, который больше не является наиболее подходящим, нам пора принимать вещи и двигаться дальше.

Здесь цитата из Larry Wall, создателя самого Perl:

(...), как правило, связаны с тем, что мы называем "регулярными выражениями", которые незначительно связаны с реальными регулярными выражениями. Тем не менее, этот термин вырос благодаря возможностям наших механизмов сопоставления шаблонов, поэтому я не собираюсь пытаться бороться с лингвистической необходимостью здесь. Я, однако, обычно называю их "регулярными выражениями" (или "regexen", когда Im в англосаксонском настроении).

И здесь сообщение в блоге от одного из разработчиков ядра PHP:

Поскольку статья была довольно длинной, здесь приводится краткое изложение основных моментов:

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

Регулярные выражения (по крайней мере, PCRE) могут соответствовать всем контекстным языкам. Таким образом, они могут также соответствовать хорошо сформированному HTML и почти всем другим языкам программирования.

Регулярные выражения могут соответствовать, по крайней мере, некоторым контекстно-зависимым языкам.

Соответствие регулярных выражений NP-complete. Таким образом, вы можете решить любую другую проблему NP, используя регулярные выражения.

При этом вы можете сопоставить палиндромы с регулярными выражениями, используя это:

^(?'letter'[a-z])+[a-z]?(?:\k'letter'(?'-letter'))+(?(letter)(?!))$

... что явно не имеет ничего общего с регулярными грамматиками. Подробнее здесь: http://www.regular-expressions.info/balancing.html

Ответ 10

В рубине вы можете использовать именованные группы захвата. поэтому что-то подобное будет работать -

def palindrome?(string)
  $1 if string =~ /\A(?<p>| \w | (?: (?<l>\w) \g<p> \k<l+0> ))\z/x
end

попробуйте, он работает...

1.9.2p290 :017 > palindrome?("racecar")
 => "racecar" 
1.9.2p290 :018 > palindrome?("kayak")
 => "kayak" 
1.9.2p290 :019 > palindrome?("woahitworks!")
 => nil

Ответ 11

Теперь это можно сделать в Perl. Использование рекурсивной ссылки:

if($istr =~ /^((\w)(?1)\g{-1}|\w?)$/){
    print $istr," is palindrome\n";
}

изменен на основе последней части http://perldoc.perl.org/perlretut.html

Ответ 12

/\A(?<a>|.|(?:(?<b>.)\g<a>\k<b+0>))\z/

он действителен для двигателя Oniguruma (который используется в Ruby)

взято из Прагматическая книжная полка

Ответ 13

На самом деле проще сделать это с помощью строковых манипуляций, а не с помощью регулярных выражений:

bool isPalindrome(String s1)

{

    String s2 = s1.reverse;

    return s2 == s1;
}

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

Ответ 14

В Perl (см. также Ответ Zsolt Botykai):

$re = qr/
  .                 # single letter is a palindrome
  |
  (.)               # first letter
  (??{ $re })??     # apply recursivly (not interpolated yet)
  \1                # last letter
/x;

while(<>) {
    chomp;
    say if /^$re$/; # print palindromes
}

Ответ 15

Вот мой ответ на Regex Golf 5-й уровень (Человек, план). Он работает до 7 символов с браузером Regexp (я использую Chrome 36.0.1985.143).

^(.)(.)(?:(.).?\3?)?\2\1$

Здесь один до 9 символов

^(.)(.)(?:(.)(?:(.).?\4?)?\3?)?\2\1$

Чтобы увеличить максимальное количество символов, на которые оно будет работать, вы повторно замените . на (?: (.).?\n?)?.

Ответ 16

Как указано Zchudson, определите, не является ли что-то палиндром, с обычным регулярным выражением, поскольку набор палиндрома не является обычным языком.

Я полностью не согласен с Airsource Ltd, когда он говорит, что "это не возможно" - это не тот ответ, который ищет интервьюер. Во время моего интервью я пришел к такому вопросу, когда у меня появился хороший кандидат, чтобы проверить, может ли он найти правильный аргумент, когда мы предложили ему сделать что-то неправильно. Я не хочу нанимать кого-то, кто попытается сделать что-то не так, если он лучше знает.

Ответ 17

что-то, что вы можете сделать с perl: http://www.perlmonks.org/?node_id=577368

Ответ 18

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

Регулярное выражение, которое будет соответствовать всем палиндромам, будет бесконечным. Вместо этого я предлагаю ему ограничиться либо максимальным размером палиндромов, чтобы принять; или если все палиндромы необходимы для использования как минимум для некоторого типа NDPA или просто используют простой метод разворота/равенства строк.

Ответ 19

Что касается выражения PCRE (из MizardX):

/^ (() (1)\2 |.?.?) $/

Вы протестировали его? На моем PHP 5.3 под Win XP Pro он терпит неудачу: aaaba Фактически, я слегка изменил выражение выражения, чтобы прочитать:

/^ (() (1) *\2 |.?.?) $/

Я думаю, что происходит то, что, когда внешняя пара символов привязана, остальные внутренние не являются. Это не совсем тот ответ, потому что, когда он неправильно переходит на "aaaba" и "aabaacaa", он неправильно работает на "aabaaca".

Интересно, есть ли исправление для этого, а также, Действительно ли пример Perl (по JF Sebastian/Zsolt) проходит мои тесты?

Csaba Gabor из Вены

Ответ 20

У меня нет комментариев для комментариев в строке, но регулярное выражение, предоставленное MizardX и измененное Csaba, может быть дополнительно изменено, чтобы заставить его работать в PCRE. Единственный сбой, который я нашел, - это строка single- char, но я могу проверить это отдельно.

/^((.)(?1)?\2|.)$/

Если вы можете сделать это сбоем на любых других строках, прокомментируйте.

Ответ 21

#!/usr/bin/perl

use strict;
use warnings;

print "Enter your string: ";
chop(my $a = scalar(<STDIN>));    
my $m = (length($a)+1)/2;
if( (length($a) % 2 != 0 ) or length($a) > 1 ) { 
  my $r; 
  foreach (0 ..($m - 2)){
    $r .= "(.)";
  }
  $r .= ".?";
  foreach ( my $i = ($m-1); $i > 0; $i-- ) { 
    $r .= "\\$i";
  } 
  if ( $a =~ /(.)(.).\2\1/ ){
    print "$a is a palindrome\n";
  }
  else {
    print "$a not a palindrome\n";
 }
exit(1);
}
print "$a not a palindrome\n";

Ответ 22

Из теории автоматов невозможно совместить палиандр любой длины (потому что для этого требуется бесконечное количество памяти). Но ВОЗМОЖНО, чтобы соответствовать Paliandromes фиксированной длины. Скажем, можно написать регулярное выражение, которое соответствует всем палиандромам длины <= 5 или <= 6 и т.д., Но не >= 5 и т.д., Где верхняя граница неясна.

Ответ 23

В Ruby вы можете использовать \b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z])\b для соответствия словам палиндрома, таким как a, dad, radar, racecar, and redivider. ps: это регулярное выражение соответствует только словам палиндрома, длина которых нечетное число букв.

Посмотрите, как это регулярное выражение соответствует радару. Граница слов \b совпадает с началом строки. Механизм регулярных выражений вводит слово "слово" группы захвата. [a-z] соответствует r, который затем сохраняется в стеке для группы "letter" группы захвата при нулевом уровне рекурсии. Теперь механизм регулярных выражений входит в первую рекурсию группы "word" . (? 'letter' [a-z]) соответствует и фиксирует a на уровне рекурсии. Регулярное выражение входит во вторую рекурсию группы "word" . (? 'letter' [a-z]) фиксирует d на втором уровне рекурсии. В течение следующих двух рекурсий группа захватывает a и r на уровнях три и четыре. Пятая рекурсия завершается неудачей, потому что в строке для символа [a-z] нет символов. Двигатель регулярных выражений должен возвращаться.

Механизм регулярных выражений теперь должен попробовать вторую альтернативу внутри группы "word" . Второй [a-z] в регулярном выражении соответствует окончательному r в строке. Теперь двигатель выходит из успешной рекурсии, переходя на один уровень до третьей рекурсии.

После сопоставления (& word) двигатель достигает \k'letter + 0 '. Ошибка backreference завершается неудачей, потому что механизм регулярных выражений уже достиг конца строки темы. Так что он снова возвращается. Вторая альтернатива теперь соответствует а. Двигатель регулярных выражений выходит из третьей рекурсии.

Механизм регулярных выражений снова сопоставлен (& word) и ему необходимо снова выполнить обратную ссылку. Backreference указывает +0 или текущий уровень рекурсии, который равен 2. На этом уровне группа захвата сопоставлена d. Ошибка backreference из-за того, что следующий символ в строке равен r. Откат снова, вторая альтернатива соответствует d.

Теперь\k'letter + 0 'соответствует второй а в строке. Это потому, что двигатель регулярных выражений вернулся к первой рекурсии, в течение которой группа захвата соответствовала первой а. Двигатель regex выходит из первой рекурсии.

Механизм регулярных выражений теперь выходит за пределы рекурсии. Что этот уровень, группа захвата сохранена r. Теперь backreference может соответствовать окончательному r в строке. Поскольку двигатель больше не находится внутри какой-либо рекурсии, он продолжается с остальной частью регулярного выражения после группы. \b соответствует в конце строки. Достигнут конец регулярного выражения, и радар возвращается в качестве общего соответствия.

Ответ 24

здесь есть код PL/SQL, который указывает, является ли заданная строка палиндром или нет, используя регулярные выражения:

create or replace procedure palin_test(palin in varchar2) is
 tmp varchar2(100);
 i number := 0;
 BEGIN
 tmp := palin;
 for i in 1 .. length(palin)/2 loop
  if length(tmp) > 1 then  
    if regexp_like(tmp,'^(^.).*(\1)$') = true then 
      tmp := substr(palin,i+1,length(tmp)-2);
    else 
      dbms_output.put_line('not a palindrome');
      exit;
    end if;
  end if;  
  if i >= length(palin)/2 then 
   dbms_output.put_line('Yes ! it is a palindrome');
  end if;
 end loop;  
end palin_test;

Ответ 25

Небольшое усовершенствование метода Airsource Ltd в псевдокоде:

WHILE string.length > 1
    IF /(.)(.*)\1/ matches string
        string = \2
    ELSE
        REJECT
ACCEPT

Ответ 26

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

/(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?).?\9\8\7\6\5\4\3\2\1/

Это будет соответствовать всем палиндромам длиной до 19 символов.

Программно решение для всех длин тривиально:

str == str.reverse ? true : false

Ответ 27

Вы также можете сделать это, не используя рекурсию:

\A(?:(.)(?=.*?(\1\2?)\z))*?.?\2\z

или исключить пустую строку:

\A(?=.)(?:(.)(?=.*?(\1\2?)\z))*?.?\2\z

Работает с Perl, PCRE, Ruby, Java

демо

Ответ 28

my $pal = 'malayalam';

while($pal=~/((.)(.*)\2)/){                                 #checking palindrome word
    $pal=$3;
}
if ($pal=~/^.?$/i){                                         #matches single letter or no letter
    print"palindrome\n";
}
else{
    print"not palindrome\n";
}