正则表达式 - 如何使用正则表达式检查字符串是回文?

这是一个我无法回答的面试问题:

如何使用正则表达式检查字符串是回文?

附: 已经有一个问题“如何检查给定的字符串是否是回文?” 它以不同的语言提供了很多答案,但没有使用正则表达式的答案。

30个解决方案
119 votes

这个问题的答案是“这是不可能的”。 更具体地说,面试官想知道你是否在计算理论课上引起了注意。

在您的计算理论课中,您学习了有限状态机。 有限状态机由节点和边组成。 每个边都用有限字母表中的字母注释。 一个或多个节点是特殊的“接受”节点,一个节点是“开始”节点。 当从给定的单词中读取每个字母时,我们遍历机器中的给定边缘。 如果我们最终处于接受状态,那么我们就说机器“接受”了这个词。

正则表达式总是可以转换为等效的有限状态机。 也就是说,接受和拒绝与正则表达式相同的单词(在现实世界中,一些正则表达式语言允许任意函数,这些不计算)。

建立一个接受所有回文的有限状态机是不可能的。 证据依赖于我们可以轻松构建一个需要任意大量节点的字符串的事实,即字符串

a ^ x b a ^ x(例如,aba,aabaa,aaabaaa,aaaabaaaa,....)

其中a ^ x是重复的x次。 这需要至少x个节点,因为在看到'b'之后我们必须重新计算x次以确保它是回文。

最后,回到最初的问题,你可以告诉采访者你可以编写一个正则表达式,接受所有小于某个有限固定长度的回文。 如果有一个真实世界的应用需要识别回文,那么它几乎肯定不会包含任意长的回答,因此这个答案将表明你可以将理论上的不可能性与现实世界的应用区分开来。 实际的正则表达式相当长,比同等的4行程序长得多(读者容易练习:写一个识别回文的程序)。

Jose M Vidal answered 2019-06-04T09:18:45Z
42 votes

虽然PCRE引擎确实支持递归正则表达式(请参阅Peter Krauss的回答),但您无法在ICU引擎上使用正则表达式(例如Apple使用的),无需额外代码即可实现此目的。 你需要做这样的事情:

这可以检测任何回文,但确实需要一个循环(这是必需的,因为正则表达式不能计数)。

$a = "teststring";
while(length $a > 1)
{
   $a =~ /(.)(.*)(.)/;
   die "Not a palindrome: $a" unless $1 eq $3;
   $a = $2;
}
print "Palindrome";
Airsource Ltd answered 2019-06-04T09:19:15Z
26 votes

这是不可能的。 回文不是由常规语言定义的。 (参见,我在计算理论中学到了一些东西)

ZCHudson answered 2019-06-04T09:19:39Z
22 votes

使用Perl正则表达式:

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

尽管如此,正如许多人所指出的那样,如果你想要严格要求,这不能被视为正则表达式。 正则表达式不支持递归。

Markus Jarderot answered 2019-06-04T09:20:09Z
11 votes

这是一个检测四字母回文(例如:契约),适用于任何类型的角色:

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

这是一个检测5个字母的回文(例如:雷达),只检查字母:

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

因此,似乎我们需要为每个可能的字长度使用不同的正则表达式。Python邮件列表上的这篇文章包含了一些有关原因的细节(有限状态自动机和泵浦引理)。

FOR answered 2019-06-04T09:20:46Z
10 votes

是的,你可以在.Net中完成!

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

你可以在这里查看! 这是一个很棒的帖子!

kev answered 2019-06-04T09:21:16Z
9 votes

根据你的自信程度,我会给出这个答案:

我不会常规做   表达。 这不合适   使用正则表达式。

Jon Skeet answered 2019-06-04T09:21:46Z
7 votes

正如一些人已经说过的那样,没有单一的正则表达式可以检测到开箱即用的普通回文,但是如果你想检测到一定长度的回文,你可以使用像

(.?)(.?)(.?)(.?)(.?).?\5\4\3\2\1
Stewart answered 2019-06-04T09:22:10Z
7 votes

StackOverflow充满了诸如“正则表达式?nope之类的答案,他们不支持它。他们无法支持它。”

事实是正则表达式与常规语法无关。 现代正则表达式具有递归和平衡组等功能,并且其实现的可用性也在不断增长(例如,请参阅此处的Ruby示例)。 在我看来,坚持认为我们领域中的正则表达式不是编程概念的旧观点只会适得其反。 我们现在是时候接受事物并继续前进,而不是讨厌那些不再是最合适的词语选择。

以下是Perl本身的创建者Larry Wall的一句话:

(...)通常与我们称之为“正则表达式”的东西有关,这些正则表达式与真正的正则表达式只是略微相关。 尽管如此,这个术语随着模式匹配引擎的功能而增长,所以我不打算在这里尝试对抗语言需求。 然而,我会将它们称为“正则表达式”(或“regexen”,当我处于盎格鲁 - 撒克逊的情绪时)。

这是PHP核心开发人员之一的博客文章:

由于文章很长,这里总结一下要点:

  • 程序员使用的“正则表达式”与形式语言理论背景下的规则性原始概念几乎没有共同之处。
  • 正则表达式(至少是PCRE)可以匹配所有无上下文的语言。 因此,它们也可以匹配格式良好的HTML和几乎所有其他编程语言。
  • 正则表达式可以匹配至少一些上下文相关语言。
  • 正则表达式的匹配是NP完全的。 因此,您可以使用正则表达式解决任何其他NP问题。

话虽这么说,你可以使用这个匹配回文与正则表达式:

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

...这显然与常规语法无关。
更多信息:[http://www.regular-expressions.info/balancing.html]

rr- answered 2019-06-04T09:24:08Z
4 votes

在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 
Taylor answered 2019-06-04T09:24:39Z
4 votes

它现在可以在Perl中完成。 使用递归引用:

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

基于近最后一部分修改[http://perldoc.perl.org/perlretut.html]

Hui Liu answered 2019-06-04T09:25:10Z
3 votes
/\A(?<a>|.|(?:(?<b>.)\g<a>\k<b+0>))\z/

它适用于Oniguruma引擎(在Ruby中使用)

取自Pragmatic Bookshelf

mpugach answered 2019-06-04T09:25:41Z
3 votes

递归正则表达式可以做到!

这么简单且不言而喻的算法来检测包含回文的字符串:

   (\w)(?:(?R)|\w?)\1

在rexegg.com/regex-recursion上,该教程解释了它是如何工作的。


它适用于任何语言,这里使用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

对比

正则表达式$subjects执行相同的工作,但是是/不是“包含”。
PS:它使用的定义“o”不是palimbrome,“able-elba”的hyphened格式不是回文,但“ableelba”是。 命名它定义1。
当“o”和“able-elba”是回文时,命名定义。

与另一个“回文正则表达”相比,

  • $subjects上面没有\w限制的base-regex,接受“able-elba”。

  • $subjects(@LilDevil)使用definition2(接受“o”和“able-elba”,因此在识别“aaaaa”和“bbbb”字符串方面也有所不同)。

  • $subjects(@Markus)未检测到“kook”既没有“bbbb”

  • $subjects(@Csaba)使用definition2。


注意:要比较,您可以在$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";
Peter Krauss answered 2019-06-04T09:27:33Z
2 votes

使用字符串操作而不是正则表达式实际上更容易:

bool isPalindrome(String s1)

{

    String s2 = s1.reverse;

    return s2 == s1;
}

我意识到这并没有真正回答面试问题,但你可以用它来展示你如何知道一个更好的方法来完成一项任务,而你不是典型的“有锤子的人,他把每一个问题视为钉子“。

Dan answered 2019-06-04T09:28:06Z
2 votes

在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
}
jfs answered 2019-06-04T09:28:30Z
2 votes

关于PCRE表达式(来自MizardX):

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

你测试过吗? 在Win XP Pro下的PHP 5.3上,它失败了:aaaba实际上,我稍微修改了表达式表达式,如下所示:

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

我认为正在发生的事情是,虽然外部的一对角色是锚定的,但剩下的内部角色却没有。 这不完全是答案,因为虽然它错误地传递了“aaaba”和“aabaacaa”,但它确实在“aabaaca”上失败了。

我想知道是否有这方面的解决方案,而且,Perl示例(由JF Sebastian / Zsolt提供)是否正确通过了我的测试?

来自维也纳的Csaba Gabor

answered 2019-06-04T09:29:35Z
2 votes

这是我对Regex Golf的第5级答案(男人,计划)。 它可以使用浏览器的Regexp最多7个字符(我使用的是Chrome 36.0.1985.143)。

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

这是最多9个字符的一个

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

要增加它的最大字符数,你需要反复替换。 用(?:(。)。?\ n?)?

pbatey answered 2019-06-04T09:30:14Z
1 votes

正如ZCHudson指出的那样,确定某些事情是否是一个通常的正则表达式无法完成,因为回文集不是常规语言。

我完全不同意Airsource有限公司,他说“这不可能”并不是面试官所寻求的那种答案。 在我的采访中,当我面对一个好的候选人时,我会遇到这样的问题,当我们建议他做错事时,检查他是否能找到正确的论点。 如果他知道更好的话,我不想聘请那些试图做错事的人。

Nicolas answered 2019-06-04T09:30:46Z
1 votes

你可以用perl做的事情:[http://www.perlmonks.org/?node_id=577368]

Zsolt Botykai answered 2019-06-04T09:31:11Z
1 votes

我会向面试官解释说,由回文组成的语言不是常规语言,而是无语境。

与所有回文匹配的正则表达式将是无限的。 相反,我建议他限制自己接受最大尺寸的回文; 或者如果需要所有回文,至少使用某种类型的NDPA,或者只使用简单的字符串反转/等于技术。

Flame answered 2019-06-04T09:31:44Z
1 votes

在捕获组用完之前,您可以使用正则表达式做到最好:

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

这将匹配所有最多19个字符的回文。

以编程方式解决所有长度是微不足道的:

str == str.reverse ? true : false
Chris answered 2019-06-04T09:32:23Z
1 votes

我还没有内联评论,但是MizardX提供的正则表达式由Csaba修改,可以进一步修改以使其在PCRE中工作。 我发现的唯一失败是单字符串字符串,但我可以单独测试它。

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

如果您可以在任何其他字符串上失败,请发表评论。

Lil Devil answered 2019-06-04T09:33:02Z
1 votes
#!/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";
sapam answered 2019-06-04T09:33:20Z
1 votes

从自动机理论来看,它不可能与任何长度的综合症相匹配(因为这需要无限量的记忆)。 但是,有可能匹配固定长度的Paliandromes。说它可以编写一个匹配所有长度&lt; = 5或&lt; = 6等的paliandromes的正则表达式,但不是&gt; = 5等,其中上限不清楚

Vijeenrosh P.W answered 2019-06-04T09:33:46Z
1 votes

在Ruby中,您可以使用\b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z])\b来匹配回文单词,例如a, dad, radar, racecar, and redivider.ps:此正则表达式仅匹配奇数字母长的回文单词。

让我们看看这个正则表达式如何匹配雷达。 边界\ b一词在字符串的开头匹配。 正则表达式引擎进入捕获组“word”。 [a-z]匹配r,然后将其存储在堆栈中,用于递归级别为零的捕获组“字母”。 现在,正则表达式引擎进入组“word”的第一次递归。 (?'letter'[a-z])匹配并捕获递归级别1。 正则表达式进入组“单词”的第二次递归。 (?'letter'[a-z])在递归级别2捕获d。 在接下来的两次递归中,该组捕获a和r三级和四级。 第五次递归失败,因为字符串中没有字符可供[a-z]匹配。 正则表达式引擎必须回溯。

正则表达式引擎现在必须在组“word”中尝试第二种选择。 正则表达式中的第二个[a-z]匹配字符串中的最后一个r。 引擎现在退出成功的递归,从一级回到第三次递归。

匹配(&amp; word)后,引擎达到\ k'letter + 0'。 反向引用失败,因为正则表达式引擎已到达主题字符串的末尾。 所以它再次回溯。 第二种选择现在与a匹配。 正则表达式引擎从第三次递归退出。

正则表达式引擎再次匹配(&amp; word)并需要再次尝试反向引用。 反向引用指定+0或当前递归级别,即2.在此级别,捕获组匹配d。 反向引用失败,因为字符串中的下一个字符是r。 再次回溯,第二种选择匹配d。

现在,\ k'letter + 0'匹配字符串中的第二个a。 那是因为正则表达式引擎已经回到第一次递归,在此期间捕获组匹配第一次a。 正则表达式引擎退出第一次递归。

正则表达式引擎现在回到所有递归之外。 这个级别,捕获组存储了r。 反向引用现在可以匹配字符串中的最后一个r。 由于引擎不再在任何递归内部,因此它继续在该组之后的正则表达式的剩余部分。 \ b匹配字符串的末尾。 到达正则表达式的末尾并且雷达作为整体匹配返回。

Melih Altıntaş answered 2019-06-04T09:34:57Z
1 votes

这里是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;
ankush answered 2019-06-04T09:35:21Z
0 votes

Airsource Ltd的方法略有改进,采用伪代码:

WHILE string.length > 1
    IF /(.)(.*)\1/ matches string
        string = \2
    ELSE
        REJECT
ACCEPT
Stewart answered 2019-06-04T09:35:46Z
0 votes

您也可以在不使用递归的情况下执行此操作:

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

或排除空字符串:

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

适用于Perl,PCRE,Ruby,Java

演示

Casimir et Hippolyte answered 2019-06-04T09:36:26Z
0 votes

我的朋友='马拉雅拉姆';

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";
}
Kanchan Sen Laskar answered 2019-06-04T09:36:51Z
0 votes

\b([a-z])?([a-z])?([a-z])?\2\1\b/gi

匹配5个字母的回文,如推荐和皮划艇。 它使用任意三个字母的(非贪婪)匹配,然后是第二个和第一个匹配的字母。

使用此链接到regex101站点

Josh answered 2019-06-04T09:37:30Z
translate from https://stackoverflow.com:/questions/233243/how-to-check-that-a-string-is-a-palindrome-using-regular-expressions