那是一个我无法回答的面试问题：
如何使用正则表达式检查字符串是否为回文？
ps 已经有一个问题“如何检查给定的字符串是否为回文？ ”它给出了很多不同语言的答案，但没有使用正则表达式的答案。
Airini
问问题
87447 次
32 回答
169
这个问题的答案是“不可能”。更具体地说，面试官想知道你是否在计算理论课上集中注意力。
在您的计算理论课上，您了解了有限状态机。有限状态机由节点和边组成。每条边都用有限字母表中的一个字母进行注释。一个或多个节点是特殊的“接受”节点，一个节点是“开始”节点。当从给定单词中读取每个字母时，我们会遍历机器中的给定边。如果我们最终处于接受状态，那么我们就说机器“接受”了这个词。
正则表达式总是可以翻译成等效的有限状态机。也就是说，接受和拒绝与正则表达式相同的单词（在现实世界中，一些正则表达式语言允许任意函数，这些不计算在内）。
不可能建立一个接受所有回文的有限状态机。证明依赖于这样一个事实，即我们可以很容易地构建一个需要任意大量节点的字符串，即字符串
a^xba^x（例如，aba、aabaa、aaabaaa、aaaabaaaa、...）
其中 a^x 是重复 x 次。这至少需要 x 个节点，因为在看到“b”之后，我们必须倒数 x 次以确保它是回文。
最后，回到最初的问题，你可以告诉面试官，你可以编写一个正则表达式来接受所有小于某个有限固定长度的回文。如果有一个现实世界的应用程序需要识别回文，那么它几乎肯定不会包括任意长的回文，因此这个答案将表明您可以将理论上的不可能与现实世界的应用区分开来。尽管如此，实际的正则表达式会很长，比等效的 4 行程序长得多（对读者来说很容易练习：编写一个识别回文的程序）。
于 2008-10-29T18:41:09.530 回答
47
虽然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";
于 2008-10-24T12:26:55.257 回答
35
这是不可能的。回文不是由常规语言定义的。（看，我确实在计算理论中学到了一些东西）
于 2008-10-24T12:25:11.347 回答
29
使用 Perl 正则表达式：
/^((.)(?1)\2|.?)$/
但是，正如许多人指出的那样，如果您想严格要求，这不能被视为正则表达式。正则表达式不支持递归。
于 2008-10-24T12:35:45.007 回答
18
对于任何类型的字符，这是一个检测 4 字母回文（例如：契约）的方法：
\(.\)\(.\)\2\1
这是一个检测 5 个字母的回文（例如：radar），只检查字母：
\([a-z]\)\([a-z]\)[a-z]\2\1
所以似乎我们需要为每个可能的字长使用不同的正则表达式。 Python 邮件列表上的这篇文章包括一些关于原因的详细信息（有限状态自动机和泵引理）。
于 2008-10-24T12:22:36.843 回答
15
根据您的自信程度，我会给出以下答案：
我不会用正则表达式来做。这不是正则表达式的适当使用。
于 2008-10-24T12:22:13.550 回答
14
于 2010-07-12T04:08:28.597 回答
13
StackOverflow 充满了诸如“正则表达式？不，他们不支持它。他们不能支持它。”之类的答案。
事实是，正则表达式不再与正则语法有任何关系。现代正则表达式具有递归和平衡组等功能，并且其实现的可用性不断增长（例如，请参见此处的 Ruby 示例）。在我看来，坚持认为我们领域中的正则表达式不是编程概念的旧观念只会适得其反。与其因为不再是最合适的词选择而讨厌他们，而是我们接受事物并继续前进的时候了。
这是Perl 本身的创建者Larry Wall 的一句话：
（……）通常与我们所说的“正则表达式”有关，它们与真正的正则表达式关系不大。尽管如此，这个术语随着我们模式匹配引擎的功能而增长，所以我不打算在这里与语言的必要性作斗争。然而，我通常会称它们为“正则表达式”（或“正则表达式”，当我处于盎格鲁-撒克逊语境中时）。
由于文章比较长，这里总结一下要点：
- 程序员使用的“正则表达式”与形式语言理论背景下的原始规则概念几乎没有共同之处。
- 正则表达式（至少 PCRE）可以匹配所有上下文无关语言。因此，它们也可以匹配格式良好的 HTML 和几乎所有其他编程语言。
- 正则表达式至少可以匹配一些上下文相关的语言。
- 正则表达式的匹配是 NP 完全的。因此，您可以使用正则表达式解决任何其他 NP 问题。
话虽如此，您可以使用以下方法将回文与正则表达式匹配：
^(?'letter'[a-z])+[a-z]?(?:\k'letter'(?'-letter'))+(?(letter)(?!))$
...这显然与常规语法无关。
更多信息在这里：http ://www.regular-expressions.info/balancing.html
于 2015-02-23T14:38:43.130 回答
9
正如一些人已经说过的那样，没有一个单一的正则表达式可以检测到开箱即用的一般回文，但是如果你想检测到一定长度的回文，你可以使用类似的东西
(.?)(.?)(.?)(.?)(.?).?\5\4\3\2\1
于 2009-09-21T08:32:31.347 回答
7
现在可以在 Perl 中完成。使用递归引用：
if($istr =~ /^((\w)(?1)\g{-1}|\w?)$/){
print $istr," is palindrome\n";
}
根据最近的最后一部分修改http://perldoc.perl.org/perlretut.html
于 2014-03-07T21:50:19.503 回答
6
在 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
于 2012-06-28T13:54:34.450 回答
6
递归正则表达式可以做到！
如此简单且不言而喻的算法来检测包含回文的字符串：
(\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”是。将其命名为定义1。
当 "o" 和 "able-elba" 是回文时，命名为definition2。
与另一个“回文正则表达式”相比，
^((.)(?:(?1)|.?)\2)$上面的基本正则表达式没有\w限制，接受“able-elba”。^((.)(?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";
于 2018-02-04T13:37:08.077 回答
5
这是我对Regex Golf 第 5 级（一个人，一个计划）的回答。它适用于浏览器的 Regexp 最多 7 个字符（我使用的是 Chrome 36.0.1985.143）。
^(.)(.)(?:(.).?\3?)?\2\1$
这是一个最多 9 个字符的
^(.)(.)(?:(.)(?:(.).?\4?)?\3?)?\2\1$
为了增加它可以工作的最大字符数，你会反复替换.? 与(?:(.).?\n?)? .
于 2014-08-20T22:12:42.253 回答
4
使用字符串操作而不是正则表达式实际上更容易做到这一点：
bool isPalindrome(String s1)
{
String s2 = s1.reverse;
return s2 == s1;
}
我意识到这并不能真正回答面试问题，但你可以用它来展示你如何知道更好的完成任务的方法，而且你不是典型的“拿着锤子的人，把每个问题都看成钉子” 。”
于 2008-10-24T12:25:45.713 回答
4
关于 PCRE 表达式（来自 MizardX）：
/^((.)(?1)\2|.?)$/
你测试过吗？在我的 Win XP Pro 下的 PHP 5.3 上它失败了：aaaba 实际上，我稍微修改了表达式表达式，改为：
/^((.)(?1)*\2|.?)$/
我认为正在发生的事情是，虽然外部的一对角色被锚定了，但其余的内部角色却没有。这并不是完整的答案，因为虽然它错误地传递了“aaaba”和“aabaacaa”，但它确实在“aabaaca”上失败了。
我想知道是否有对此进行修复，以及 Perl 示例（由 JF Sebastian / Zsolt 编写）是否正确通过了我的测试？
来自维也纳的 Csaba Gabor
于 2009-03-10T13:06:40.750 回答
4
于 2016-05-26T10:41:07.700 回答
3
在 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
}
于 2008-11-03T22:04:04.967 回答
2
正如ZCHudson所指出的，确定某事是否是回文无法使用通常的正则表达式来完成，因为回文集不是常规语言。
当Airsource Ltd 说“这不可能”不是面试官想要的答案时，我完全不同意他的看法。在我的面试中，当我面对一个好的候选人时，我会提出这样的问题，以检查当我们向他提出做错事时，他是否能找到正确的论点。我不想雇用一个如果他知道更好的人就会试图以错误的方式做某事的人。
于 2008-10-24T13:30:39.390 回答
2
你可以用 perl 做些什么：http ://www.perlmonks.org/?node_id=577368
于 2008-10-24T20:44:35.830 回答
2
我会向面试官解释，由回文组成的语言不是常规语言，而是上下文无关的。
匹配所有回文的正则表达式将是无限的。相反，我建议他将自己限制在可以接受的最大回文数；或者如果需要所有回文，至少使用某种类型的 NDPA，或者只使用简单的字符串反转/等于技术。
于 2008-12-17T18:22:59.820 回答
2
在用完捕获组之前，您可以使用正则表达式做的最好的事情：
/(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?).?\9\8\7\6\5\4\3\2\1/
这将匹配长度不超过 19 个字符的所有回文。
以编程方式解决所有长度是微不足道的：
str == str.reverse ? true : false
于 2011-10-30T13:10:36.853 回答
2
我还没有代表内联评论，但是 MizardX 提供并由 Csaba 修改的正则表达式可以进一步修改以使其在 PCRE 中工作。我发现的唯一失败是单字符字符串，但我可以单独测试。
/^((.)(?1)?\2|.)$/
如果您可以使其在任何其他字符串上失败，请发表评论。
于 2012-03-09T18:59:56.010 回答
2
#!/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";
于 2013-01-10T05:10:19.310 回答
2
从自动机理论来看，它不可能匹配任何长度的回文（因为这需要无限量的内存）。但是有可能匹配固定长度的回文。说它可以编写一个匹配所有长度 <= 5 或 <= 6 等回文数的正则表达式，但不匹配 >=5 等上限不清楚的地方
于 2013-08-15T18:30:34.643 回答
2
在 Ruby 中，您可以使用\b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z])\b来匹配回文词，例如a, dad, radar, racecar, and redivider. ps：这个正则表达式只匹配长度为奇数个字母的回文词。
让我们看看这个正则表达式如何匹配雷达。单词边界 \b 在字符串的开头匹配。正则表达式引擎输入捕获组“word”。[az] 匹配 r，然后将其存储在递归级别为零的捕获组“字母”的堆栈中。现在正则表达式引擎进入组“word”的第一个递归。(?'letter'[az]) 在递归级别 1 匹配并捕获 a。正则表达式输入组“单词”的第二次递归。(?'letter'[az]) 在递归级别 2 捕获 d。在接下来的两次递归中，该组在第三和第四级捕获 a 和 r。第五次递归失败，因为字符串中没有字符可供 [az] 匹配。正则表达式引擎必须回溯。
正则表达式引擎现在必须尝试组“word”中的第二种选择。正则表达式中的第二个 [az] 匹配字符串中的最后一个 r。引擎现在从成功的递归中退出，返回到第三次递归。
在匹配 (&word) 之后，引擎到达 \k'letter+0'。反向引用失败，因为正则表达式引擎已经到达主题字符串的末尾。于是又一次回溯。第二种选择现在与 a 匹配。正则表达式引擎退出第三次递归。
正则表达式引擎再次匹配 (&word)，需要再次尝试反向引用。反向引用指定 +0 或当前的递归级别，即 2。在此级别，捕获组匹配 d。反向引用失败，因为字符串中的下一个字符是 r。再次回溯，第二个选择匹配 d。
现在，\k'letter+0' 匹配字符串中的第二个 a。这是因为正则表达式引擎已经返回到捕获组匹配第一个 a 的第一个递归。正则表达式引擎退出第一个递归。
正则表达式引擎现在回到所有递归之外。即这个级别，捕获组存储了 r。反向引用现在可以匹配字符串中的最后一个 r。由于引擎不再在任何递归内部，因此它继续执行组之后的正则表达式的其余部分。\b 匹配字符串的末尾。到达正则表达式的末尾，雷达作为整体匹配返回。
于 2014-09-08T10:14:11.083 回答
2
这是 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;
于 2015-12-15T07:08:34.943 回答
2
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";
}
于 2017-01-29T18:23:40.277 回答
2
此正则表达式将检测最多 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
于 2020-02-06T00:52:30.470 回答
0
Airsource Ltd 方法的轻微改进，伪代码：
WHILE string.length > 1
IF /(.)(.*)\1/ matches string
string = \2
ELSE
REJECT
ACCEPT
于 2009-09-21T08:17:26.487 回答
0
\b([a-z])?([a-z])?([a-z])?\2\1\b/gi
匹配 5 个字母回文，例如 refer 和 kayak。它使用任意三个字母的（非贪婪）匹配来做到这一点，然后是第二个和第一个匹配的字母。
于 2018-01-03T15:59:29.200 回答
0
在 JavaScript 中，它是通过键入来完成的
function palindrome(str) {
var symbol = /\W|_/g;
str = str.replace(symbol, "").toLowerCase();
var palindrome = str.split("").reverse("").join("");
return (str === palindrome);
}
于 2018-05-19T15:53:34.263 回答