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

Question

这是我无法回答的面试问题：

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

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

- Airini

---

https://dev59.com/l3A65IYBdhLWcg3wxBmr 可以提供一个思路。 - unknown_boundaries

现在（2018年）如果您正在寻找“回文正则表达式”，请参阅Prakhar的链接中关于PCRE支持递归模式的讨论，以及我的递归正则表达式和比较。 - Peter Krauss

Answer 1

这个问题的答案是“不可能”。更具体地说，面试官想知道你在计算理论课上是否专心听讲。

在计算理论课上，你学习了关于有限状态机的知识。有限状态机由节点和边组成。每条边都带有一个来自有限字母表的字母。一个或多个节点是特殊的“接受”节点，而一个节点是“起始”节点。当从给定单词中读取每个字母时，我们会在机器中遍历给定的边缘。如果我们最终停留在接受状态，则意味着该机器“接受”该单词。

正则表达式可以总是被翻译成等价的有限状态机。也就是说，它们接受和拒绝与正则表达式相同的单词（在现实世界中，一些正则表达式语言允许任意函数，这些不算）。

无法构建一个接受所有回文字符串的有限状态机。证明依赖于以下事实：我们可以轻松构建需要任意大数量的节点的字符串，即

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

其中 a^x 重复 x 次。这至少需要 x 个节点，因为在看到 'b' 后，我们必须倒数 x 次来确保它是回文。

最后，回到原始问题，你可以告诉面试官，你可以编写一个正则表达式，接受所有小于某个有限固定长度的回文。如果有任何需要识别回文的实际应用程序，几乎肯定不会包含任意长的回文，因此这个答案将显示你可以区分理论上的不可能性和现实世界中的应用。但是，实际的正则表达式会相当冗长，比等效的四行程序要长得多（读者的简单练习：编写一个标识回文的程序）。

- jmvidal

---

在Ruby 1.9.x中，正则表达式不再是自动机理论意义上的“Regular”，因此可以检查回文等操作。然而，就意图和目的而言，不能用一个“Regular”正则表达式来检查回文（明白吗？）。 - user131441

@SteveMoser 这里有一篇关于 Ruby 正则表达式引擎（>=1.9）的好文章，链接在这里：http://pragprog.com/magazines/2010-12/whats-new-in-ruby- - user131441

@John，所以在这个问题的背景下，Jose是正确的，而hqt是错误的。 - Steve Moser

在学术领域中，正则表达式具有特定的边界（定义了一个DFA）。但实际上，许多正则表达式引擎（主要是Perl及其相关方言）支持反向引用，这违反了学术定义（变成了NFA甚至更广泛的表达式）。因此，这个问题的答案取决于提问者的参考框架。 - jiggy

在口试中，你应该说“从正规角度来讲是不可能的”，但你应该指出有些正则表达式引擎是允许这样做的。 - Oliver A.

在面试中，我会确保注意发音和拼写。 - trincot

Answer 2

虽然PCRE引擎支持递归正则表达式（请参见Peter Krauss的答案），但你不能在ICU引擎上（例如由苹果使用）使用正则表达式来实现此功能而无需额外的代码。您需要像这样执行：

这会检测任何回文，但确实需要一个循环（因为正则表达式不能计数）。

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

- Airsource Ltd

---

好的回答。问题并没有要求一个直接检测回文的单个正则表达式 - 它只是要求使用正则表达式来检测回文的方法。恭喜您通过这种方式进行思考。 - Stewart

另请参阅仅使用一个正则表达式进行最简匹配（无字符串操作）的方法，https://dev59.com/_nVC5IYBdhLWcg3woCnN#48608623 - Peter Krauss

谢谢@PeterKrauss。我不知道PCRE有递归功能。我引用了你的答案。 - Airsource Ltd

Answer 3

不可能。回文并未由正则语言定义。（看，我在计算理论中确实学到了一些东西）

- ZCHudson

---

大多数正则表达式引擎捕获的内容不仅限于常规语言（例如，.NET可以捕获匹配的括号）。只有标准的正则表达式受到常规语言的限制。 - Santiago Palladino

这个问题确实使用了“正则表达式”这个术语...所以ZCHudson的答案是正确的。 - oz10

@austirg：ZCHudson的回答是正确的，但不完整。现代编程语言中使用的正则表达式和理论计算机科学课程中使用的正则表达式是不同的东西。这个术语只是历史遗留问题。请参见https://dev59.com/_nVC5IYBdhLWcg3woCnN和我的回答。 - jfs

@J.F. Sebastian - 我必须同意 austirg 的观点。当没有特定的编程语言提到时，正则表达式一词就适用于计算机科学的定义。并非所有支持正则表达式的语言都能做到这一点，因此我们不应该假设在这里使用的语言可以这样做。 - Rontologist

@Rontologist：我在问题中没有看到对编程语言的限制，因此任何语言都是允许的。看一下右边：在相关问题中，“正则表达式”的含义是什么？它们中有没有提到特定的编程语言？ - jfs

Answer 4

使用 Perl 正则表达式：

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

尽管许多人已经指出，如果您想严格要求，这不能被视为正则表达式。正则表达式不支持递归。

虽然许多人已经指出，如果你想严格要求的话，这不能算作一个正则表达式。正则表达式不支持递归。

- MizardX

---

这在 PCRE 中不起作用（它不匹配“ababa”），但在 Perl 5.10 中可以正常工作。 - newacct

你是对的。PCRE似乎将递归视为原子组，而Perl允许其中回溯。我认为在PCRE中不可能进行此检查。 - Markus Jarderot

出人意料的是，它不适用于非拉丁语言，例如亚美尼亚语。 - Temujin

@Temujin 可能是因为 Unicode 字符被匹配为编码字节（添加 /u 修饰符），或者因为组合字符（使用 \X 转义序列 替换 .）。 - Markus Jarderot

它不能匹配像 anna, aa 这样的字符串。将其修改为 ^((\w)(?:\2*$|(?:(?1)|\w?)\2))$。而且Casimirs Regex不使用递归也可以很好地工作，除了不能匹配单个字符，但这可能是有意的。 - bobble bubble

我的模式在PCRE中无法工作。但是在Perl中可以。 当子字符串重复时，您的模式会失败。例如abababa。使用基于PCRE的正则表达式引擎时，不可能为每个输入都使用递归使其工作。 Casimir的正则表达式采用了不同的方法，使用迭代和可变状态，非常迷人。 - Markus Jarderot

Answer 5

这里有一个用于检测任何类型字符的长度为4的回文（例如：deed）的方法：

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

这里有一个用于检测5个字母回文（例如：radar）的方法，只检查字母：

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

看起来我们需要针对每个可能的单词长度使用不同的正则表达式。这篇关于Python邮件列表的帖子详细介绍了为什么需要这样做（有限状态自动机和泵引理）。

- FOR

---

能否请您解释一下针对5个字母回文的正则表达式？ - MohaMed

Answer 6

根据您的信心水平，我会给出这个答案：

我不会用正则表达式来完成。这不是正则表达式的恰当使用方式。

- Jon Skeet

---

我希望你能多解释一些，以表明你真正理解正则表达式的局限性。你简单的回答可能会被理解为“我被难住了”。 - Scott Wegner

因此，他给出了依赖子句。 - Will Bickford

Answer 7

是的，你可以在 .Net 中实现它！

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

你可以在这里查看！这是一篇精彩的文章！

- kev

---

.NET风格的正则表达式的整个意义在于它们不是常规的，因为它们不是有限状态自动机；从理论上讲，它们并不真正是正则表达式。 - cat

Answer 8

StackOverflow上充斥着像“正则表达式？不，它们不支持。它们不能支持。”这样的答案。

事实上，现代正则表达式已经与正则语法没有任何关系了。现代正则表达式具有递归和平衡组等功能，并且它们的实现可用性越来越高（例如，在这里查看Ruby示例）。在我看来，坚持旧信念认为我们领域中的正则表达式不过是一种编程概念，只会产生反效果。与其因为词汇选择不再最合适而憎恨它们，不如接受事实并继续前进。

以下是Perl创始人 Larry Wall的引用：

“……通常与我们所谓的‘正则表达式’有关，这些表达式与真正的正则表达式只有边缘联系。尽管如此，随着我们的模式匹配引擎的功能增强，该术语已经发展起来，因此我不打算在这里与语言必要性作斗争。但是，通常情况下我会称它们为‘regexes’（或者当我处于盎格鲁-撒克逊心境时，称之为‘regexen’）。”

这里有一篇博客文章，作者是PHP核心开发者：

由于文章比较长，以下是主要内容的摘要：

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

话虽如此，您可以使用正则表达式匹配回文，方法如下：

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

"...这显然与常规语法无关。
更多信息请参见：http://www.regular-expressions.info/balancing.html。"

- rr-

Answer 9

正如一些人已经说过的那样，没有一个单一的正则表达式可以直接检测出通用回文，但是如果你想检测某个长度范围内的回文，你可以使用以下代码：

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

- Stewart

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

demo

- Casimir et Hippolyte

---

这是一个非常有趣的正则表达式问题的答案。实际上，这是唯一一个通过了我的一些测试的模式（https://regex101.com/r/4mw2tF/1/tests）。感谢您的分享，Casimir :) - bobble bubble

@bobblebubble：感谢您的支持。正如您所看到的，我最近编辑了这个答案，因为之前的版本是错误的（三年了，真是太丢人了）。 - Casimir et Hippolyte