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

Question

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

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

ps已经有一个问题" 如何检查给定的字符串是否是回文？ "它提供了很多不同语言的答案,但没有使用正则表达式的答案.

Answer 1

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

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

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

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

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

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

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

Answer 2

虽然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";

Answer 3

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

Answer 4

使用Perl正则表达式:

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

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

Answer 5

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

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

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

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

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

Answer 6

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

我不会用正则表达式来做.它不适合使用正则表达式.

Answer 7

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

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

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

Answer 8

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

Answer 9

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

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

Answer 10

你也可以不使用递归来做到这一点：

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

允许单个字符：

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

适用于 Perl、PCRE

演示

对于 Java：

\A(?:(.)(?=.*?(\1\2\z|(?<!(?=\2\z).{0,1000})\1\z)))*?.?\2\z

演示

Answer 11

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

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

根据最后一部分进行了修改http://perldoc.perl.org/perlretut.html

Answer 12

在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 

Answer 13

实际上，使用字符串操作比使用正则表达式更容易：

bool isPalindrome(String s1)

{

    String s2 = s1.reverse;

    return s2 == s1;
}

我意识到这并不能真正回答面试问题，但是您可以使用它来展示如何知道更好的完成任务的方法，而且您不是典型的“拿着锤子的人”，他把所有问题都视为钉子”。

Answer 14

这是我对Regex Golf 的第 5 级（一个人，一个计划）的回答。它适用于浏览器的 Regexp 最多 7 个字符（我使用的是 Chrome 36.0.1985.143）。

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

这是最多 9 个字符的一个

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

要增加它适用的最大字符数，您需要反复替换.? 与(?:(.).?\n?)? .

Answer 15

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

如此简单且不言而喻的算法来检测包含回文的字符串：

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

比较中

正则表达式^((\w)(?:(?1)|\w?)\2)$ 执行相同的工作，但是是/否是“包含”。
PS：它使用的定义中，“ o”不是文物，“ able-elba”连字符格式不是回文，而是“ ableelba”。命名为definition1。
当“ o”和“ able-elba”为回文教鞭时，命名为definition2。

与其他“回文正则表达式”相比，

• ^((.)(?:(?1)|.?)\2)$上面的base-regex \w不受限制地接受“ able-elba”。

• ^((.)(?1)?\2|.)$（@LilDevil）使用definition2（接受“ o”和“ able-elba”，因此在识别“ aaaaa”和“ bbbb”字符串方面也有所不同）。

• ^((.)(?1)\2|.?)$（@Markus）未检测到“ kook”，也未检测到“ bbbb”

• ^((.)(?1)*\2|.?)$（@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";