Как проверить, что строка является палиндромом с помощью регулярных выражений?
Это был вопрос интервью, на который я не смог ответить:
Как проверить, что строка является палиндромом с помощью регулярных выражений?
ps Уже есть вопрос " Как проверить, является ли данная строка палиндромом?", и она дает много ответов на разных языках, но нет ответа, который использует регулярные выражения.
31 ответ
Ответ на этот вопрос заключается в том, что "это невозможно". В частности, интервьюер задается вопросом, обратили ли вы внимание на уроке теории вычислительной техники.
В вашем классе теории вычислений вы узнали о конечных автоматах. Конечный автомат состоит из узлов и ребер. Каждое ребро снабжено буквой из конечного алфавита. Один или несколько узлов являются специальными "принимающими" узлами, а один узел является "начальным" узлом. Поскольку каждая буква читается из заданного слова, мы пересекаем заданное ребро в машине. Если мы оказываемся в состоянии принятия, то мы говорим, что машина "принимает" это слово.
Регулярное выражение всегда можно перевести в эквивалентный конечный автомат. То есть тот, который принимает и отклоняет те же слова, что и регулярное выражение (в реальном мире некоторые языки регулярного выражения допускают произвольные функции, они не учитываются).
Невозможно построить конечный автомат, который принимает все палиндромы. Доказательство основано на том факте, что мы можем легко построить строку, которая требует сколь угодно большого количества узлов, а именно строки
^x b a^x (например, аба, аабаа, ааабааа, аааабаааа....)
где ^ х повторяется х раз. Это требует как минимум x узлов, потому что после просмотра 'b' мы должны отсчитать x раз, чтобы убедиться, что это палиндром.
Наконец, возвращаясь к исходному вопросу, вы можете сказать интервьюеру, что вы можете написать регулярное выражение, которое принимает все палиндромы, которые меньше некоторой конечной фиксированной длины. Если существует какое-либо реальное приложение, которое требует идентификации палиндромов, то оно почти наверняка не будет включать произвольно длинные, поэтому этот ответ покажет, что вы можете отличить теоретические невозможности от реальных приложений. Тем не менее, фактическое регулярное выражение будет довольно длинным, намного длиннее, чем эквивалентная четырехстрочная программа (простое упражнение для читателя: напишите программу, которая идентифицирует палиндромы).
Хотя механизм PCRE поддерживает рекурсивные регулярные выражения (см. Ответ Питера Краусса), вы не можете использовать регулярное выражение в механизме ICU (как, например, используется Apple), чтобы достичь этого без дополнительного кода. Вам нужно будет сделать что-то вроде этого:
Это обнаруживает любой палиндром, но действительно требует цикла (который будет необходим, потому что регулярные выражения не могут считать).
$a = "teststring";
while(length $a > 1)
{
$a =~ /(.)(.*)(.)/;
die "Not a palindrome: $a" unless $1 eq $3;
$a = $2;
}
print "Palindrome";
Это невозможно. Палиндромы не определяются обычным языком. (Смотри, я узнал кое-что в вычислительной теории)
С регулярным выражением Perl:
/^((.)(?1)\2|.?)$/
Хотя, как отмечали многие, это нельзя считать регулярным выражением, если вы хотите быть строгим. Регулярные выражения не поддерживают рекурсию.
Вот один для обнаружения 4-буквенных палиндромов (например, деяние) для любого типа персонажа:
\(.\)\(.\)\2\1
Вот один, чтобы обнаружить 5-буквенные палиндромы (например: радар), проверяя только буквы:
\([a-z]\)\([a-z]\)[a-z]\2\1
Так что, похоже, нам нужно другое регулярное выражение для каждой возможной длины слова. Этот пост в списке рассылки Python содержит некоторые подробности о том, почему (конечные автоматы и лемма прокачки).
В зависимости от того, насколько вы уверены, я бы дал такой ответ:
Я бы не стал делать это с регулярным выражением. Это не правильное использование регулярных выражений.
Да, вы можете сделать это в.Net!
(?<N>.)+.?(?<-N>\k<N>)+(?(N)(?!))
Вы можете проверить это здесь! Это замечательный пост!
Stackru полон ответов типа "Регулярные выражения? Нет, они не поддерживают его. Они не могут его поддержать".
Правда в том, что регулярные выражения больше не имеют ничего общего с регулярными грамматиками. Современные регулярные выражения имеют функции, такие как группы рекурсии и балансировки, и доступность их реализаций постоянно возрастает (см., Например, примеры Ruby здесь). По моему мнению, держаться за старое убеждение, что регулярные выражения в нашей области - это что-то, кроме концепции программирования, просто контрпродуктивно. Вместо того, чтобы ненавидеть их за слово "выбор", которое больше не является наиболее подходящим, нам пора принять вещи и двигаться дальше.
Вот цитата из Ларри Уолла, создателя самого Perl:
(…) Обычно связанные с тем, что мы называем "регулярными выражениями", которые лишь незначительно связаны с реальными регулярными выражениями. Тем не менее, термин расширился с возможностями наших механизмов сопоставления с образцом, поэтому я не буду пытаться бороться с лингвистической необходимостью здесь. Однако я обычно буду называть их "регулярными выражениями" (или "регулярными выражениями", когда я нахожусь в англосаксонском настроении).
А вот сообщение в блоге одного из разработчиков ядра PHP:
Поскольку статья была довольно длинной, вот краткое изложение основных моментов:
- "Регулярные выражения", используемые программистами, имеют очень мало общего с исходным понятием регулярности в контексте теории формального языка.
- Регулярные выражения (по крайней мере, PCRE) могут соответствовать всем контекстно-свободным языкам. Как таковые они могут также соответствовать правильно сформированному HTML и почти всем другим языкам программирования.
- Регулярные выражения могут соответствовать по крайней мере некоторым контекстно-зависимым языкам.
- Сопоставление регулярных выражений является NP-полным. Таким образом, вы можете решить любую другую проблему NP, используя регулярные выражения.
При этом, вы можете сопоставить палиндромы с регулярными выражениями, используя это:
^(?'letter'[a-z])+[a-z]?(?:\k'letter'(?'-letter'))+(?(letter)(?!))$
... что, очевидно, не имеет ничего общего с обычными грамматиками.
Более подробная информация здесь: http://www.regular-expressions.info/balancing.html
Как уже говорили некоторые, не существует единственного регулярного выражения, которое бы обнаруживало общий палиндром из коробки, но если вы хотите обнаружить палиндромы до определенной длины, вы можете использовать что-то вроде
(.?)(.?)(.?)(.?)(.?).?\5\4\3\2\1
Вы также можете сделать это без использования рекурсии:
\A(?:(.)(?=.*?(\1\2?)\z))*?.?\2\z
или исключить пустую строку:
\A(?=.)(?:(.)(?=.*?(\1\2?)\z))*?.?\2\z
Работает с Perl, PCRE, Ruby, Java
Теперь это можно сделать в Perl. Используя рекурсивную ссылку:
if($istr =~ /^((\w)(?1)\g{-1}|\w?)$/){
print $istr," is palindrome\n";
}
изменено на основе последней части http://perldoc.perl.org/perlretut.html
Рекурсивные регулярные выражения могут сделать это!
Итак, простой и самоочевидный алгоритм обнаружения строки, содержащей палиндром:
(\w)(?:(?R)|\w?)\1
На http://www.rexegg.com/regex-recursion.html руководство объясняет, как это работает.
Он отлично работает с любым языком, вот пример, адаптированный из того же источника (ссылка), что и для проверки концепции, с использованием PHP:
$subjects=['dont','o','oo','kook','book','paper','kayak','okonoko','aaaaa','bbbb'];
$pattern='/(\w)(?:(?R)|\w?)\1/';
foreach ($subjects as $sub) {
echo $sub." ".str_repeat('-',15-strlen($sub))."-> ";
if (preg_match($pattern,$sub,$m))
echo $m[0].(($m[0]==$sub)? "! a palindrome!\n": "\n");
else
echo "sorry, no match\n";
}
выходы
dont ------------> sorry, no match
o ---------------> sorry, no match
oo --------------> oo! a palindrome!
kook ------------> kook! a palindrome!
book ------------> oo
paper -----------> pap
kayak -----------> kayak! a palindrome!
okonoko ---------> okonoko! a palindrome!
aaaaa -----------> aaaaa! a palindrome!
bbbb ------------> bbb
Сравнение
Регулярное выражение ^((\w)(?:(?1)|\w?)\2)$ сделать ту же работу, но так как да / нет вместо "содержит".
PS: он использует определение, где "o" не является палимбромом, а дефисный формат "able-elba" - это не палиндром, а "ableelba". Называя это определение1.
Когда "o" и "able-elba" являются палиндронами, называются определения2.
Сравнивая с другими "регулярными выражениями палиндрома",
^((.)(?:(?1)|.?)\2)$базовое выражение выше без\wограничение, принимая "способный Эльба".^((.)(?1)?\2|.)$( @LilDevil) Используйте определение 2 (принимает "o" и "able-elba", которые отличаются также распознаванием строк "aaaaa" и "bbbb").^((.)(?1)\2|.?)$( @Markus) не обнаружил ни "kook", ни "bbbb"^((.)(?1)*\2|.?)$( @Csaba) Используйте определение2.
ПРИМЕЧАНИЕ: для сравнения вы можете добавить больше слов на $subjects и строка для каждого сравниваемого регулярного выражения,
if (preg_match('/^((.)(?:(?1)|.?)\2)$/',$sub)) echo " ...reg_base($sub)!\n";
if (preg_match('/^((.)(?1)?\2|.)$/',$sub)) echo " ...reg2($sub)!\n";
if (preg_match('/^((.)(?1)\2|.?)$/',$sub)) echo " ...reg3($sub)!\n";
if (preg_match('/^((.)(?1)*\2|.?)$/',$sub)) echo " ...reg4($sub)!\n";
В ruby вы можете использовать именованные группы захвата. так что-то вроде этого будет работать -
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
На самом деле это проще сделать с помощью строковых операций, чем с помощью регулярных выражений:
bool isPalindrome(String s1)
{
String s2 = s1.reverse;
return s2 == s1;
}
Я понимаю, что на самом деле это не отвечает на вопрос интервью, но вы могли бы использовать его, чтобы показать, как вы знаете лучший способ выполнения задачи, и вы не типичный "человек с молотком, который видит каждую проблему как гвоздь ".
Вот мой ответ на 5-й уровень Regex Golf (Человек, план). Он работает до 7 символов с помощью браузера Regexp (я использую Chrome 36.0.1985.143).
^(.)(.)(?:(.).?\3?)?\2\1$
Вот один до 9 символов
^(.)(.)(?:(.)(?:(.).?\4?)?\3?)?\2\1$
Чтобы увеличить максимальное количество символов, на которое он будет работать, вы должны будете неоднократно его заменять . с (?:(.).?\n?)?,
Относительно выражения PCRE (из MizardX):
/^((.)(?1)\2|.?)$/
Вы проверяли это? На моем PHP 5.3 под Win XP Pro происходит сбой: aaaba На самом деле я немного изменил выражение, чтобы оно читалось:
/^((.)(?1)*\2|.?)$/
Я думаю, что в то время как внешняя пара символов привязана, остальные внутренние - нет. Это не совсем полный ответ, потому что, хотя он неверно передает слова "aaaba" и "aabaacaa", он действительно ошибочно указывает на "aabaaca".
Интересно, есть ли исправление для этого, а также, правильно ли проходит тест Perl (автор JF Sebastian / Zsolt)?
Чаба Габор из Вены
/\A(?<a>|.|(?:(?<b>.)\g<a>\k<b+0>))\z/
это действительно для движка Oniguruma (который используется в Ruby)
взял с прагматичной книжной полки
Это регулярное выражение обнаружит палиндромы длиной до 22 символов, игнорируя пробелы, табуляции, запятые и кавычки.
\b(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*\11?[ \t,'"]*\10|\10?)[ \t,'"]*\9|\9?)[ \t,'"]*\8|\8?)[ \t,'"]*\7|\7?)[ \t,'"]*\6|\6?)[ \t,'"]*\5|\5?)[ \t,'"]*\4|\4?)[ \t,'"]*\3|\3?)[ \t,'"]*\2|\2?))?[ \t,'"]*\1\b
Поиграйте с ним здесь: https://regexr.com/4tmui
В Perl (см. Также ответ Жолта Ботыкай):
$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
}
Что вы можете сделать с Perl: http://www.perlmonks.org/?node_id=577368
Мой $pal='малалайам';
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";
}
Вот код 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;
Из теории автоматов невозможно сопоставить палиандром любой длины (потому что это требует бесконечного количества памяти). Но ВОЗМОЖНО соответствовать палиандромам фиксированной длины. Скажем, можно написать регулярное выражение, которое соответствует всем палиандромам длиной <= 5 или <= 6 и т. Д., Но не>=5 и т. Д., Если верхняя граница неясна
В Ruby вы можете использовать \b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z])\b соответствовать палиндромным словам, таким как a, dad, radar, racecar, and redivider, ps: это регулярное выражение соответствует только палиндромным словам, длина которых нечетная.
Давайте посмотрим, как это регулярное выражение соответствует радар. Граница слова \b соответствует началу строки. Движок регулярных выражений входит в группу захвата "слово". [az] соответствует r, который затем сохраняется в стеке для группы захвата "буква" на нулевом уровне рекурсии. Теперь движок регулярных выражений входит в первую рекурсию группы "Слово". (?'letter'[az]) соответствует и захватывает a на уровне рекурсии один. Регулярное выражение входит во вторую рекурсию группы "слово". (?'letter'[az]) захватывает d на втором уровне рекурсии. Во время следующих двух рекурсий группа захватывает a и r на уровнях три и четыре. Пятая рекурсия завершается неудачно, потому что в строке не осталось символов для совпадения [az]. Двигатель регулярных выражений должен вернуться назад.
Движок регулярных выражений теперь должен попробовать второй вариант внутри группы "слово". Второе [az] в регулярном выражении соответствует последнему r в строке. Двигатель теперь выходит из успешной рекурсии, возвращаясь на один уровень вверх к третьей рекурсии.
После сопоставления (&word) двигатель достигает \k'letter+0'. Обратной ссылки не удается, потому что механизм регулярных выражений уже достиг конца строки темы. Так что это возвращается еще раз. Второй вариант теперь соответствует a. Движок регулярных выражений выходит из третьей рекурсии.
Движок регулярных выражений снова соответствует (&word) и должен снова попытаться выполнить обратную ссылку. Обратная ссылка указывает +0 или текущий уровень рекурсии, который равен 2. На этом уровне группа захвата соответствует d. Обратная ссылка не выполняется, потому что следующий символ в строке - r. Снова откат, второй вариант соответствует d.
Теперь \ k'letter + 0 'соответствует второму a в строке. Это связано с тем, что движок регулярных выражений вернулся с первой рекурсии, во время которой группа захвата соответствовала первой a. Движок регулярных выражений выходит из первой рекурсии.
Движок регулярных выражений теперь находится за пределами всей рекурсии. Что на этом уровне группа захвата хранится r. Теперь обратная ссылка может соответствовать финальному r в строке. Поскольку движок больше не находится внутри какой-либо рекурсии, он продолжает работу с остатком регулярного выражения после группы. \b соответствует концу строки. Конец регулярного выражения достигнут, и радар возвращается как общий матч.
#!/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";
Лучшее, что вы можете сделать с регулярными выражениями, прежде чем вы исчерпаете группы захвата:
/(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?).?\9\8\7\6\5\4\3\2\1/
Это будет соответствовать всем палиндромам длиной до 19 символов.
Программное решение для всех длин тривиально:
str == str.reverse ? true : false
У меня пока нет комментариев для комментирования, но регулярное выражение, предоставленное MizardX и измененное Csaba, можно изменить, чтобы оно работало в PCRE. Единственный сбой, который я обнаружил - это строка из одного символа, но я могу проверить это отдельно.
/^((.)(?1)?\2|.)$/
Если вы можете заставить его выйти из строя на любых других строках, пожалуйста, прокомментируйте.
Я бы объяснил интервьюеру, что язык, состоящий из палиндромов, не является обычным языком, а является контекстно-свободным.
Регулярное выражение, которое будет соответствовать всем палиндромам, будет бесконечным. Вместо этого я бы предложил, чтобы он ограничился либо максимальным размером палиндромов, чтобы принять; или если все палиндромы необходимы, используйте как минимум некоторый тип NDPA, или просто используйте простой метод обращения строк / равно.
Как указывает ZCHudson, определить, является ли что-то палиндромом, нельзя с помощью обычного регулярного выражения, поскольку набор палиндрома не является регулярным языком.
Я полностью не согласен с Airsource Ltd, когда он говорит, что "это невозможно" - это не тот ответ, который ищет интервьюер. Во время моего интервью я сталкиваюсь с таким вопросом, когда сталкиваюсь с хорошим кандидатом, чтобы проверить, сможет ли он найти правильный аргумент, когда мы предложили ему сделать что-то не так. Я не хочу нанимать кого-то, кто попытается сделать что-то неправильно, если он знает что-то лучшее.
\b([a-z])?([a-z])?([a-z])?\2\1\b/gi
Соответствует 5-буквенным палиндромам, таким как отсылка и каяк. Это делается с использованием (не жадного) сопоставления любых трех букв, за которыми следуют 2-я и 1-я совпадающие буквы.