That was an interview question that I was unable to answer:
那是一个我无法回答的面试问题:
How to check that a string is a palindrome using regular expressions?
如何使用正则表达式检查字符串是否是回文?
p.s. There is already a question "How to check if the given string is palindrome?" and it gives a lot of answers in different languages, but no answer that uses regular expressions.
还有一个问题“如何检查给定的字符串是否是palindrome?”它用不同的语言给出了很多答案,但是没有使用正则表达式的答案。
31 个解决方案
#1
116
The answer to this question is that "it is impossible". More specifically, the interviewer is wondering if you paid attention in your computational theory class.
这个问题的答案是“不可能”。更具体地说,面试官想知道你在计算理论课上有没有注意到。
In your computational theory class you learned about finite state machines. A finite state machine is composed of nodes and edges. Each edge is annotated with a letter from a finite alphabet. One or more nodes are special "accepting" nodes and one node is the "start" node. As each letter is read from a given word we traverse the given edge in the machine. If we end up in an accepting state then we say that the machine "accepts" that word.
在计算理论课上,你们学过有限状态机。有限状态机由节点和边组成。每条边都附有有限字母表中的字母。一个或多个节点是特殊的“接受”节点,一个节点是“开始”节点。当每个字母从一个给定的单词中读取时,我们会遍历机器中给定的边缘。如果我们最终处于接受状态,那么我们说机器“接受”那个词。
A regular expression can always be translated into an equivalent finite state machine. That is, one that accepts and rejects the same words as the regular expression (in the real world, some regexp languages allow for arbitrary functions, these don't count).
正则表达式总是可以转换为等效的有限状态机。也就是说,它接受并拒绝与正则表达式相同的词(在现实世界中,某些regexp语言允许任意的函数,这些不算数)。
It is impossible to build a finite state machine that accepts all palindromes. The proof relies on the facts that we can easily build a string that requires an arbitrarily large number of nodes, namely the string
建立一个有限状态机来接受所有的回文是不可能的。证明依赖于这样的事实:我们可以轻松构建一个需要任意数量的节点的字符串,即字符串
a^x b a^x (eg., aba, aabaa, aaabaaa, aaaabaaaa, ....)
x(如一个b x ^ ^。、aba、aabaa aaabaaa、aaaabaaaa ....)
where a^x is a repeated x times. This requires at least x nodes because, after seeing the 'b' we have to count back x times to make sure it is a palindrome.
在^ x乘以x是一个重复。这至少需要x个节点,因为在看到“b”之后,我们必须计算x次,以确保它是一个回文。
Finally, getting back to the original question, you could tell the interviewer that you can write a regular expression that accepts all palindromes that are smaller than some finite fixed length. If there is ever a real-world application that requires identifying palindromes then it will almost certainly not include arbitrarily long ones, thus this answer would show that you can differentiate theoretical impossibilities from real-world applications. Still, the actual regexp would be quite long, much longer than equivalent 4-line program (easy exercise for the reader: write a program that identifies palindromes).
最后,回到最初的问题,你可以告诉面试官你可以写一个正则表达式,接受所有小于有限固定长度的回文。如果有一个真实的应用程序需要识别回文,那么它几乎肯定不会包含任意长的回文,因此这个答案将表明您可以区分理论的不可能性和实际的应用程序。尽管如此,实际的regexp将相当长,比等效的4行程序长得多(对于读者来说很容易:编写一个识别回文的程序)。
#2
42
While the PCRE engine does support recursive regular expressions (see the answer by Peter Krauss), you cannot use a regex on the ICU engine (as used, for example, by Apple) to achieve this without extra code. You'll need to do something like this:
虽然PCRE引擎确实支持递归正则表达式(请参阅Peter Krauss的答案),但是如果没有额外的代码,就不能在ICU引擎上使用regex(例如,苹果)来实现这一点。你需要做这样的事情:
This detects any palindrome, but does require a loop (which will be required because regular expressions can't count).
这将检测任何回文,但确实需要一个循环(这将是必需的,因为正则表达式不能计数)。
$a = "teststring";
while(length $a > 1)
{
$a =~ /(.)(.*)(.)/;
die "Not a palindrome: $a" unless $1 eq $3;
$a = $2;
}
print "Palindrome";
#3
26
It's not possible. Palindromes aren't defined by a regular language. (See, I DID learn something in computational theory)
这是不可能的。回文不是由常规语言定义的。(看,我在计算理论中确实学到了一些东西)
#4
21
With Perl regex:
与Perl正则表达式:
/^((.)(?1)\2|.?)$/
Though, as many have pointed out, this can't be considered a regular expression if you want to be strict. Regular expressions does not support recursion.
但是,正如许多人指出的那样,如果您想严格一点,就不能将其视为正则表达式。正则表达式不支持递归。
#5
11
Here's one to detect 4-letter palindromes (e.g.: deed), for any type of character:
这里有一个用于检测任何类型的字符的4字母回文(如:契据):
\(.\)\(.\)\2\1
Here's one to detect 5-letter palindromes (e.g.: radar), checking for letters only:
这里有一个用于检测5个字母的回文(例如:radar),只检查字母:
\([a-z]\)\([a-z]\)[a-z]\2\1
So it seems we need a different regex for each possible word length. This post on a Python mailing list includes some details as to why (Finite State Automata and pumping lemma).
因此,我们似乎需要一个不同的正则表达式来表示每个可能的单词长度。Python邮件列表中的这篇文章包含了为什么(有限状态自动机和抽取引理)的一些细节。
#6
10
Yes, you can do it in .Net!
是的,你可以在。net中完成!
(?<N>.)+.?(?<-N>\k<N>)+(?(N)(?!))
You can check it here! It's a wonderful post!
你可以在这里查看!这是一个精彩的文章!
#7
9
Depending on how confident you are, I'd give this answer:
取决于你有多自信,我的回答是:
I wouldn't do it with a regular expression. It's not an appropriate use of regular expressions.
我不会用正则表达式。它不是正则表达式的合适用法。
#8
7
As a few have already said, there's no single regexp that'll detect a general palindrome out of the box, but if you want to detect palindromes up to a certain length, you can use something like
正如一些人已经说过的,没有任何一个regexp可以从盒子中检测到一般的回文,但是如果您想要检测到一定长度的回文,可以使用类似的方法
(.?)(.?)(.?)(.?)(.?).?\5\4\3\2\1
#9
6
* is full of answers like "Regular expressions? nope, they don't support it. They can't support it.".
*上满是“正则表达式?”不,他们不支持。他们不能支持它。”。
The truth is that regular expressions have nothing to do with regular grammars anymore. Modern regular expressions feature functions such as recursion and balancing groups, and the availability of their implementations is ever growing (see Ruby examples here, for instance). In my opinion, hanging onto old belief that regular expressions in our field are anything but a programming concept is just counterproductive. Instead of hating them for the word choice that is no longer the most appropriate, it is time for us to accept things and move on.
事实是正则表达式不再与正则语法有关。现代正则表达式具有递归和平衡组等功能,其实现的可用性也在不断增加(例如,请参阅这里的Ruby示例)。在我看来,坚持我们领域中的正则表达式绝不是编程概念的旧观念只会适得其反。我们不应该因为“选择”这个词而憎恨他们,因为这个词已经不再是最合适的了,现在是我们接受事物并继续前进的时候了。
Here's a quote from Larry Wall, the creator of Perl itself:
以下是Perl本身的创建者Larry Wall的一句话:
(…) generally having to do with what we call “regular expressions”, which are only marginally related to real regular expressions. Nevertheless, the term has grown with the capabilities of our pattern matching engines, so I’m not going to try to fight linguistic necessity here. I will, however, generally call them “regexes” (or “regexen”, when I’m in an Anglo-Saxon mood).
(…)通常与我们所说的“正则表达式”有关,它只与真正的正则表达式稍有关联。然而,这个术语已经随着我们的模式匹配引擎的能力而增长了,所以我不打算在这里对抗语言的必要性。然而,我通常会称它们为“regexes”(或“regexen”,当我处于盎格鲁-撒克逊情绪中时)。
And here's a blog post by one of PHP's core developers:
下面是PHP核心开发人员的一篇博文:
As the article was quite long, here a summary of the main points:
由于这篇文章很长,这里总结一下要点:
- The “regular expressions” used by programmers have very little in common with the original notion of regularity in the context of formal language theory.
- 在形式语言理论的背景下,程序员使用的“正则表达式”与原来的正则概念几乎没有共同之处。
- Regular expressions (at least PCRE) can match all context-free languages. As such they can also match well-formed HTML and pretty much all other programming languages.
- 正则表达式(至少是PCRE)可以匹配所有上下文无关的语言。因此,它们也可以匹配格式良好的HTML和几乎所有其他编程语言。
- Regular expressions can match at least some context-sensitive languages.
- 正则表达式至少可以匹配一些上下文敏感的语言。
- Matching of regular expressions is NP-complete. As such you can solve any other NP problem using regular expressions.
- 正则表达式的匹配是np完备的。因此,您可以使用正则表达式解决任何其他NP问题。
That being said, you can match palindromes with regexes using this:
也就是说,你可以用这个来匹配回文和正则表达式:
^(?'letter'[a-z])+[a-z]?(?:\k'letter'(?'-letter'))+(?(letter)(?!))$
...which obviously has nothing to do with regular grammars.
More info here: http://www.regular-expressions.info/balancing.html
…这显然与常规语法无关。更多信息:http://www.regular-expressions.info/balancing.html
#10
4
In ruby you can use named capture groups. so something like this will work -
在ruby中,可以使用命名的捕获组。所以像这样的东西会起作用。
def palindrome?(string)
$1 if string =~ /\A(?<p>| \w | (?: (?<l>\w) \g<p> \k<l+0> ))\z/x
end
try it, it works...
试一试,效果……
1.9.2p290 :017 > palindrome?("racecar")
=> "racecar"
1.9.2p290 :018 > palindrome?("kayak")
=> "kayak"
1.9.2p290 :019 > palindrome?("woahitworks!")
=> nil
#11
4
It can be done in Perl now. Using recursive reference:
现在可以用Perl完成。使用递归引用:
if($istr =~ /^((\w)(?1)\g{-1}|\w?)$/){
print $istr," is palindrome\n";
}
modified based on the near last part http://perldoc.perl.org/perlretut.html
修改的基础上的最后一个部分http://perldoc.perl.org/perlretut.html。
#12
3
/\A(?<a>|.|(?:(?<b>.)\g<a>\k<b+0>))\z/
it is valid for Oniguruma engine (which is used in Ruby)
它适用于Oniguruma引擎(在Ruby中使用)
took from Pragmatic Bookshelf
从务实的书架
#13
2
It's actually easier to do it with string manipulation rather than regular expressions:
实际上,使用字符串操作更容易,而不是正则表达式:
bool isPalindrome(String s1)
{
String s2 = s1.reverse;
return s2 == s1;
}
I realize this doesn't really answer the interview question, but you could use it to show how you know a better way of doing a task, and you aren't the typical "person with a hammer, who sees every problem as a nail."
我意识到这并不能真正回答面试问题,但你可以用它来展示你如何知道一种更好的完成任务的方式,而且你不是那种典型的“拿着锤子的人,把每一个问题都看成钉子”。
#14
2
In Perl (see also Zsolt Botykai's answer):
在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
}
#15
2
Regarding the PCRE expression (from MizardX):
关于PCRE表达式(来自MizardX):
/^((.)(?1)\2|.?)$/
/ ^((。)(? 1)\ 2 |。?)/美元
Have you tested it? On my PHP 5.3 under Win XP Pro it fails on: aaaba Actually, I modified the expression expression slightly, to read:
你测试过吗?我在Win XP Pro下的PHP 5.3上失败了:aaaba实际上,我稍微修改了表达式,如下所示:
/^((.)(?1)*\2|.?)$/
/ ^((。)(1)* \ 2 |。)/美元
I think what is happening is that while the outer pair of characters are anchored, the remaining inner ones are not. This is not quite the whole answer because while it incorrectly passes on "aaaba" and "aabaacaa", it does fail correctly on "aabaaca".
我认为现在的情况是,虽然外部的两个字符被固定住了,但剩下的内部字符却没有。这并不是全部的答案,因为当它错误地传递“aaaba”和“aabaacaa”时,它在“aabaaca”上正确地失败了。
I wonder whether there a fixup for this, and also, Does the Perl example (by JF Sebastian / Zsolt) pass my tests correctly?
我想知道是否对此有一个修正,而且Perl示例(JF Sebastian / Zsolt)是否通过了我的测试?
Csaba Gabor from Vienna
Csaba伽柏从维也纳
#16
2
Here's my answer to Regex Golf's 5th level (A man, a plan). It works for up to 7 characters with the browser's Regexp (I'm using Chrome 36.0.1985.143).
以下是我对Regex高尔夫第五关的回答(一个男人,一个计划)。它可以使用浏览器的Regexp处理最多7个字符(我使用的是Chrome 36.0.1985.143)。
^(.)(.)(?:(.).?\3?)?\2\1$
Here's one for up to 9 characters
这里有一个最多9个字符
^(.)(.)(?:(.)(?:(.).?\4?)?\3?)?\2\1$
To increase the max number of characters it'd work for, you'd repeatedly replace .? with (?:(.).?\n?)?.
为了增加它的最大字符数,你需要反复替换。(?:()。\ n ?)?。
#17
1
As pointed out by ZCHudson, determine if something is a palindrome cannot be done with an usual regexp, as the set of palindrome is not a regular language.
正如ZCHudson所指出的,确定一个回文是不是不能使用常规的regexp来完成,因为回文回文的集合不是一种常规语言。
I totally disagree with Airsource Ltd when he says that "it's not possibles" is not the kind of answer the interviewer is looking for. During my interview, I come to this kind of question when I face a good candidate, to check if he can find the right argument when we proposed to him to do something wrong. I do not want to hire someone who will try to do something the wrong way if he knows better one.
我完全不同意Airsource有限公司的说法,他说“不可能”不是面试官想要的回答。在我的面试中,当我遇到一个好候选人的时候,我就会问这样的问题:当我们建议他做错事的时候,他是否能找到正确的论点。我不想雇佣一个人,如果他知道更好的方法,他会尝试用错误的方式去做一些事情。
#18
1
something you can do with perl: http://www.perlmonks.org/?node_id=577368
您可以使用perl做一些事情:http://www.perlmonks.org/?node_id=577368
#19
1
I would explain to the interviewer that the language consisting of palindromes is not a regular language but instead context-free.
我要向面试官解释,由回文组成的语言不是一种常规的语言,而是与上下文无关的。
The regular expression that would match all palindromes would be infinite. Instead I would suggest he restrict himself to either a maximum size of palindromes to accept; or if all palindromes are needed use at minimum some type of NDPA, or just use the simple string reversal/equals technique.
匹配所有回文的正则表达式将是无限的。相反,我建议他把自己限制在一个最大的回文量,以便接受;或者,如果所有的回文都需要使用至少某种类型的NDPA,或者仅仅使用简单的字符串反转/equals技术。
#20
1
The best you can do with regexes, before you run out of capture groups:
在您用完捕获组之前,最好使用regexes:
/(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?).?\9\8\7\6\5\4\3\2\1/
This will match all palindromes up to 19 characters in length.
这将匹配所有的回文长度高达19个字符。
Programatcally solving for all lengths is trivial:
编程地求解所有长度是很简单的:
str == str.reverse ? true : false
#21
1
I don't have the rep to comment inline yet, but the regex provided by MizardX, and modified by Csaba, can be modified further to make it work in PCRE. The only failure I have found is the single-char string, but I can test for that separately.
我还没有代表对内联进行评论,但是MizardX提供并由Csaba修改的regex可以进一步修改,使其在PCRE中工作。我发现的唯一错误是单字符字符串,但是我可以分别测试它。
/^((.)(?1)?\2|.)$/
/ ^((。)(1)? \ 2 |。)/美元
If you can make it fail on any other strings, please comment.
如果您可以使它在任何其他字符串上失败,请评论。
#22
1
#!/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";
#23
1
From automata theory its impossible to match a paliandrome of any lenght ( because that requires infinite amount of memory). But IT IS POSSIBLE to match Paliandromes of Fixed Length. Say its possible to write a regex that matches all paliandromes of length <= 5 or <= 6 etc, but not >=5 etc where upper bound is unclear
从自动机理论来看,不可能匹配任何一种光线(因为那需要无限的内存)的paliandrome。但是有可能匹配固定长度的Paliandromes。假设可以编写一个regex来匹配长度<= 5或<= 6等的所有paliandromes,但不能编写>=5等,其中上限不明确
#24
1
In Ruby you can use \b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z])\b
to match palindrome words such as a, dad, radar, racecar, and redivider
. ps : this regex only matches palindrome words that are an odd number of letters long.
在Ruby中,你可以使用\b(?'word'(?'letter'[a-z])\g' \k'letter '\ +0'|[a-z])\b来匹配palindrome单词,如a、dad、radar、racecar和redivider。ps:这个regex只匹配奇数个字母的回文单词。
Let's see how this regex matches radar. The word boundary \b matches at the start of the string. The regex engine enters the capturing group "word". [a-z] matches r which is then stored in the stack for the capturing group "letter" at recursion level zero. Now the regex engine enters the first recursion of the group "word". (?'letter'[a-z]) matches and captures a at recursion level one. The regex enters the second recursion of the group "word". (?'letter'[a-z]) captures d at recursion level two. During the next two recursions, the group captures a and r at levels three and four. The fifth recursion fails because there are no characters left in the string for [a-z] to match. The regex engine must backtrack.
让我们看看这个regex如何匹配雷达。单词boundary \b在字符串的开头匹配。regex引擎进入捕获组“word”。[a-z]匹配r,然后将其存储在堆栈中,以便捕获组在递归0级的“字母”。现在,regex引擎将进入组“word”的第一个递归。(?“字母”[a-z])匹配并捕获递归一级的a。regex将进入组“word”的第二个递归。(?“字母”[a-z])捕获递归级别为2的d。在接下来的两个递归过程中,组在第3和第4级捕获a和r。第5次递归失败,因为字符串中没有要匹配的字符。regex引擎必须后退。
The regex engine must now try the second alternative inside the group "word". The second [a-z] in the regex matches the final r in the string. The engine now exits from a successful recursion, going one level back up to the third recursion.
regex引擎现在必须尝试组“word”中的第二个选项。regex中的第二个[a-z]匹配字符串中的最后一个r。引擎现在从一个成功的递归中退出,从一层回到第三层递归。
After matching (&word) the engine reaches \k'letter+0'. The backreference fails because the regex engine has already reached the end of the subject string. So it backtracks once more. The second alternative now matches the a. The regex engine exits from the third recursion.
匹配(&word)后,引擎到达\k'字母+0'。因为regex引擎已经到达主题字符串的末尾,所以backreference失败。所以它又回来了。第二个选项现在与a匹配。regex引擎从第三个递归中退出。
The regex engine has again matched (&word) and needs to attempt the backreference again. The backreference specifies +0 or the present level of recursion, which is 2. At this level, the capturing group matched d. The backreference fails because the next character in the string is r. Backtracking again, the second alternative matches d.
regex引擎再次匹配(&word)并需要再次尝试反向引用。backreference指定+0或当前递归级别,即2。在这个级别,捕获组匹配d。由于字符串中的下一个字符是r,所以backreference失败。
Now, \k'letter+0' matches the second a in the string. That's because the regex engine has arrived back at the first recursion during which the capturing group matched the first a. The regex engine exits the first recursion.
现在,k'字母+0'匹配字符串中的第二个a。这是因为regex引擎返回到第一个递归,在此期间捕获组匹配第一个a。
The regex engine is now back outside all recursion. That this level, the capturing group stored r. The backreference can now match the final r in the string. Since the engine is not inside any recursion any more, it proceeds with the remainder of the regex after the group. \b matches at the end of the string. The end of the regex is reached and radar is returned as the overall match.
regex引擎现在回到了所有递归之外。这个级别,捕获组存储了r。反向引用现在可以匹配字符串的最终r。由于该引擎不再属于任何递归,它将继续处理组之后的regex的其余部分。\b在字符串的末尾匹配。到达regex的末端,雷达作为整体匹配返回。
#25
1
here is PL/SQL code which tells whether given string is palindrome or not using regular expressions:
下面是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;
#26
1
Recursive Regular Expressions can do it!
So simple and self-evident algorithm to detect a string that contains a palindrome:
如此简单且自明的算法来检测包含回文的字符串:
(\w)(?:(?R)|\w?)\1
At rexegg.com/regex-recursion the tutorial explains how it works.
在rexegg.com/regex递归中,教程将解释它是如何工作的。
It works fine with any language, here an example adapted from the same source (link) as proof-of-concept, using PHP:
它适用于任何一种语言,这里有一个示例使用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";
}
outputs
输出
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
Comparing
The regular expression ^((\w)(?:(?1)|\w?)\2)$
do the same job, but as yes/not instead "contains".
PS: it is using a definition where "o" is not a palimbrome, "able-elba" hyphened format is not a palindrome, but "ableelba" is. Naming it definition1.
When "o" and "able-elba" are palindrones, naming definition2.
正则表达式^((\ w)(?:(? 1)| \ w ?)\ 2)美元做同样的工作,但随着是的/不是,而不是“包含”。它使用的定义是o不是palimbrome,“健全的elba”连字符格式不是palindrome,而是ableelba。命名它显出。当“o”和“健全的埃尔巴”是palindrone时,命名定义2。
Comparing with another "palindrome regexes",
与另一个“回文正则表达式”相比,
-
^((.)(?:(?1)|.?)\2)$
the base-regex above without\w
restriction, accepting "able-elba".^(()。(?:? 1 |。?)\ 2)美元以上base-regex没有\ w限制,接受“able-elba”。
-
^((.)(?1)?\2|.)$
(@LilDevil) Use definition2 (accepts "o" and "able-elba" so differing also in the recognition of "aaaaa" and "bbbb" strings).^((。)(1)? \ 2 |。)(@LilDevil)使用美元definition2(接受“o”和“able-elba”所以不同也承认“五星级”和“bbbb”字符串)。
-
^((.)(?1)\2|.?)$
(@Markus) not detected "kook" neither "bbbb"^((。)(? 1)\ 2 |。?)美元(@Markus)没有发现“怪人”也没有“bbbb”
-
^((.)(?1)*\2|.?)$
(@Csaba) Use definition2.^((。)(1)* \ 2 |。)(@Csaba)使用definition2美元。
NOTE: to compare you can add more words at $subjects
and a line for each compared regex,
注意:要进行比较,您可以在$subject中添加更多的单词,并为每个比较regex添加一行,
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";
#27
0
A slight refinement of Airsource Ltd's method, in pseudocode:
对Airsource Ltd的方法稍加改进,在伪代码中:
WHILE string.length > 1
IF /(.)(.*)\1/ matches string
string = \2
ELSE
REJECT
ACCEPT
#28
0
You can also do it without using recursion:
你也可以不使用递归:
\A(?:(.)(?=.*?(\1\2?)\z))*?.?\2\z
or to exclude the empty string:
或排除空字符串:
\A(?=.)(?:(.)(?=.*?(\1\2?)\z))*?.?\2\z
Works with Perl, PCRE, Ruby, Java
使用Perl、PCRE、Ruby和Java
演示
#29
0
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";
}
#30
0
\b([a-z])?([a-z])?([a-z])?\2\1\b/gi
\ b([a - z])?([a - z])?([a - z])? 2 \ \ 1 \ b / gi
Matches 5 letter palindromes such as refer and kayak. It does this using (non-greedy) matching of any three letters, followed by the 2nd and 1st matched letters.
匹配5个字母回文,如参考和kayak。它使用(非贪婪)匹配任意三个字母,然后是第二个和第一个匹配的字母。
Link to regex101 site using this
使用此链接到regex101站点
#1
116
The answer to this question is that "it is impossible". More specifically, the interviewer is wondering if you paid attention in your computational theory class.
这个问题的答案是“不可能”。更具体地说,面试官想知道你在计算理论课上有没有注意到。
In your computational theory class you learned about finite state machines. A finite state machine is composed of nodes and edges. Each edge is annotated with a letter from a finite alphabet. One or more nodes are special "accepting" nodes and one node is the "start" node. As each letter is read from a given word we traverse the given edge in the machine. If we end up in an accepting state then we say that the machine "accepts" that word.
在计算理论课上,你们学过有限状态机。有限状态机由节点和边组成。每条边都附有有限字母表中的字母。一个或多个节点是特殊的“接受”节点,一个节点是“开始”节点。当每个字母从一个给定的单词中读取时,我们会遍历机器中给定的边缘。如果我们最终处于接受状态,那么我们说机器“接受”那个词。
A regular expression can always be translated into an equivalent finite state machine. That is, one that accepts and rejects the same words as the regular expression (in the real world, some regexp languages allow for arbitrary functions, these don't count).
正则表达式总是可以转换为等效的有限状态机。也就是说,它接受并拒绝与正则表达式相同的词(在现实世界中,某些regexp语言允许任意的函数,这些不算数)。
It is impossible to build a finite state machine that accepts all palindromes. The proof relies on the facts that we can easily build a string that requires an arbitrarily large number of nodes, namely the string
建立一个有限状态机来接受所有的回文是不可能的。证明依赖于这样的事实:我们可以轻松构建一个需要任意数量的节点的字符串,即字符串
a^x b a^x (eg., aba, aabaa, aaabaaa, aaaabaaaa, ....)
x(如一个b x ^ ^。、aba、aabaa aaabaaa、aaaabaaaa ....)
where a^x is a repeated x times. This requires at least x nodes because, after seeing the 'b' we have to count back x times to make sure it is a palindrome.
在^ x乘以x是一个重复。这至少需要x个节点,因为在看到“b”之后,我们必须计算x次,以确保它是一个回文。
Finally, getting back to the original question, you could tell the interviewer that you can write a regular expression that accepts all palindromes that are smaller than some finite fixed length. If there is ever a real-world application that requires identifying palindromes then it will almost certainly not include arbitrarily long ones, thus this answer would show that you can differentiate theoretical impossibilities from real-world applications. Still, the actual regexp would be quite long, much longer than equivalent 4-line program (easy exercise for the reader: write a program that identifies palindromes).
最后,回到最初的问题,你可以告诉面试官你可以写一个正则表达式,接受所有小于有限固定长度的回文。如果有一个真实的应用程序需要识别回文,那么它几乎肯定不会包含任意长的回文,因此这个答案将表明您可以区分理论的不可能性和实际的应用程序。尽管如此,实际的regexp将相当长,比等效的4行程序长得多(对于读者来说很容易:编写一个识别回文的程序)。
#2
42
While the PCRE engine does support recursive regular expressions (see the answer by Peter Krauss), you cannot use a regex on the ICU engine (as used, for example, by Apple) to achieve this without extra code. You'll need to do something like this:
虽然PCRE引擎确实支持递归正则表达式(请参阅Peter Krauss的答案),但是如果没有额外的代码,就不能在ICU引擎上使用regex(例如,苹果)来实现这一点。你需要做这样的事情:
This detects any palindrome, but does require a loop (which will be required because regular expressions can't count).
这将检测任何回文,但确实需要一个循环(这将是必需的,因为正则表达式不能计数)。
$a = "teststring";
while(length $a > 1)
{
$a =~ /(.)(.*)(.)/;
die "Not a palindrome: $a" unless $1 eq $3;
$a = $2;
}
print "Palindrome";
#3
26
It's not possible. Palindromes aren't defined by a regular language. (See, I DID learn something in computational theory)
这是不可能的。回文不是由常规语言定义的。(看,我在计算理论中确实学到了一些东西)
#4
21
With Perl regex:
与Perl正则表达式:
/^((.)(?1)\2|.?)$/
Though, as many have pointed out, this can't be considered a regular expression if you want to be strict. Regular expressions does not support recursion.
但是,正如许多人指出的那样,如果您想严格一点,就不能将其视为正则表达式。正则表达式不支持递归。
#5
11
Here's one to detect 4-letter palindromes (e.g.: deed), for any type of character:
这里有一个用于检测任何类型的字符的4字母回文(如:契据):
\(.\)\(.\)\2\1
Here's one to detect 5-letter palindromes (e.g.: radar), checking for letters only:
这里有一个用于检测5个字母的回文(例如:radar),只检查字母:
\([a-z]\)\([a-z]\)[a-z]\2\1
So it seems we need a different regex for each possible word length. This post on a Python mailing list includes some details as to why (Finite State Automata and pumping lemma).
因此,我们似乎需要一个不同的正则表达式来表示每个可能的单词长度。Python邮件列表中的这篇文章包含了为什么(有限状态自动机和抽取引理)的一些细节。
#6
10
Yes, you can do it in .Net!
是的,你可以在。net中完成!
(?<N>.)+.?(?<-N>\k<N>)+(?(N)(?!))
You can check it here! It's a wonderful post!
你可以在这里查看!这是一个精彩的文章!
#7
9
Depending on how confident you are, I'd give this answer:
取决于你有多自信,我的回答是:
I wouldn't do it with a regular expression. It's not an appropriate use of regular expressions.
我不会用正则表达式。它不是正则表达式的合适用法。
#8
7
As a few have already said, there's no single regexp that'll detect a general palindrome out of the box, but if you want to detect palindromes up to a certain length, you can use something like
正如一些人已经说过的,没有任何一个regexp可以从盒子中检测到一般的回文,但是如果您想要检测到一定长度的回文,可以使用类似的方法
(.?)(.?)(.?)(.?)(.?).?\5\4\3\2\1
#9
6
* is full of answers like "Regular expressions? nope, they don't support it. They can't support it.".
*上满是“正则表达式?”不,他们不支持。他们不能支持它。”。
The truth is that regular expressions have nothing to do with regular grammars anymore. Modern regular expressions feature functions such as recursion and balancing groups, and the availability of their implementations is ever growing (see Ruby examples here, for instance). In my opinion, hanging onto old belief that regular expressions in our field are anything but a programming concept is just counterproductive. Instead of hating them for the word choice that is no longer the most appropriate, it is time for us to accept things and move on.
事实是正则表达式不再与正则语法有关。现代正则表达式具有递归和平衡组等功能,其实现的可用性也在不断增加(例如,请参阅这里的Ruby示例)。在我看来,坚持我们领域中的正则表达式绝不是编程概念的旧观念只会适得其反。我们不应该因为“选择”这个词而憎恨他们,因为这个词已经不再是最合适的了,现在是我们接受事物并继续前进的时候了。
Here's a quote from Larry Wall, the creator of Perl itself:
以下是Perl本身的创建者Larry Wall的一句话:
(…) generally having to do with what we call “regular expressions”, which are only marginally related to real regular expressions. Nevertheless, the term has grown with the capabilities of our pattern matching engines, so I’m not going to try to fight linguistic necessity here. I will, however, generally call them “regexes” (or “regexen”, when I’m in an Anglo-Saxon mood).
(…)通常与我们所说的“正则表达式”有关,它只与真正的正则表达式稍有关联。然而,这个术语已经随着我们的模式匹配引擎的能力而增长了,所以我不打算在这里对抗语言的必要性。然而,我通常会称它们为“regexes”(或“regexen”,当我处于盎格鲁-撒克逊情绪中时)。
And here's a blog post by one of PHP's core developers:
下面是PHP核心开发人员的一篇博文:
As the article was quite long, here a summary of the main points:
由于这篇文章很长,这里总结一下要点:
- The “regular expressions” used by programmers have very little in common with the original notion of regularity in the context of formal language theory.
- 在形式语言理论的背景下,程序员使用的“正则表达式”与原来的正则概念几乎没有共同之处。
- Regular expressions (at least PCRE) can match all context-free languages. As such they can also match well-formed HTML and pretty much all other programming languages.
- 正则表达式(至少是PCRE)可以匹配所有上下文无关的语言。因此,它们也可以匹配格式良好的HTML和几乎所有其他编程语言。
- Regular expressions can match at least some context-sensitive languages.
- 正则表达式至少可以匹配一些上下文敏感的语言。
- Matching of regular expressions is NP-complete. As such you can solve any other NP problem using regular expressions.
- 正则表达式的匹配是np完备的。因此,您可以使用正则表达式解决任何其他NP问题。
That being said, you can match palindromes with regexes using this:
也就是说,你可以用这个来匹配回文和正则表达式:
^(?'letter'[a-z])+[a-z]?(?:\k'letter'(?'-letter'))+(?(letter)(?!))$
...which obviously has nothing to do with regular grammars.
More info here: http://www.regular-expressions.info/balancing.html
…这显然与常规语法无关。更多信息:http://www.regular-expressions.info/balancing.html
#10
4
In ruby you can use named capture groups. so something like this will work -
在ruby中,可以使用命名的捕获组。所以像这样的东西会起作用。
def palindrome?(string)
$1 if string =~ /\A(?<p>| \w | (?: (?<l>\w) \g<p> \k<l+0> ))\z/x
end
try it, it works...
试一试,效果……
1.9.2p290 :017 > palindrome?("racecar")
=> "racecar"
1.9.2p290 :018 > palindrome?("kayak")
=> "kayak"
1.9.2p290 :019 > palindrome?("woahitworks!")
=> nil
#11
4
It can be done in Perl now. Using recursive reference:
现在可以用Perl完成。使用递归引用:
if($istr =~ /^((\w)(?1)\g{-1}|\w?)$/){
print $istr," is palindrome\n";
}
modified based on the near last part http://perldoc.perl.org/perlretut.html
修改的基础上的最后一个部分http://perldoc.perl.org/perlretut.html。
#12
3
/\A(?<a>|.|(?:(?<b>.)\g<a>\k<b+0>))\z/
it is valid for Oniguruma engine (which is used in Ruby)
它适用于Oniguruma引擎(在Ruby中使用)
took from Pragmatic Bookshelf
从务实的书架
#13
2
It's actually easier to do it with string manipulation rather than regular expressions:
实际上,使用字符串操作更容易,而不是正则表达式:
bool isPalindrome(String s1)
{
String s2 = s1.reverse;
return s2 == s1;
}
I realize this doesn't really answer the interview question, but you could use it to show how you know a better way of doing a task, and you aren't the typical "person with a hammer, who sees every problem as a nail."
我意识到这并不能真正回答面试问题,但你可以用它来展示你如何知道一种更好的完成任务的方式,而且你不是那种典型的“拿着锤子的人,把每一个问题都看成钉子”。
#14
2
In Perl (see also Zsolt Botykai's answer):
在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
}
#15
2
Regarding the PCRE expression (from MizardX):
关于PCRE表达式(来自MizardX):
/^((.)(?1)\2|.?)$/
/ ^((。)(? 1)\ 2 |。?)/美元
Have you tested it? On my PHP 5.3 under Win XP Pro it fails on: aaaba Actually, I modified the expression expression slightly, to read:
你测试过吗?我在Win XP Pro下的PHP 5.3上失败了:aaaba实际上,我稍微修改了表达式,如下所示:
/^((.)(?1)*\2|.?)$/
/ ^((。)(1)* \ 2 |。)/美元
I think what is happening is that while the outer pair of characters are anchored, the remaining inner ones are not. This is not quite the whole answer because while it incorrectly passes on "aaaba" and "aabaacaa", it does fail correctly on "aabaaca".
我认为现在的情况是,虽然外部的两个字符被固定住了,但剩下的内部字符却没有。这并不是全部的答案,因为当它错误地传递“aaaba”和“aabaacaa”时,它在“aabaaca”上正确地失败了。
I wonder whether there a fixup for this, and also, Does the Perl example (by JF Sebastian / Zsolt) pass my tests correctly?
我想知道是否对此有一个修正,而且Perl示例(JF Sebastian / Zsolt)是否通过了我的测试?
Csaba Gabor from Vienna
Csaba伽柏从维也纳
#16
2
Here's my answer to Regex Golf's 5th level (A man, a plan). It works for up to 7 characters with the browser's Regexp (I'm using Chrome 36.0.1985.143).
以下是我对Regex高尔夫第五关的回答(一个男人,一个计划)。它可以使用浏览器的Regexp处理最多7个字符(我使用的是Chrome 36.0.1985.143)。
^(.)(.)(?:(.).?\3?)?\2\1$
Here's one for up to 9 characters
这里有一个最多9个字符
^(.)(.)(?:(.)(?:(.).?\4?)?\3?)?\2\1$
To increase the max number of characters it'd work for, you'd repeatedly replace .? with (?:(.).?\n?)?.
为了增加它的最大字符数,你需要反复替换。(?:()。\ n ?)?。
#17
1
As pointed out by ZCHudson, determine if something is a palindrome cannot be done with an usual regexp, as the set of palindrome is not a regular language.
正如ZCHudson所指出的,确定一个回文是不是不能使用常规的regexp来完成,因为回文回文的集合不是一种常规语言。
I totally disagree with Airsource Ltd when he says that "it's not possibles" is not the kind of answer the interviewer is looking for. During my interview, I come to this kind of question when I face a good candidate, to check if he can find the right argument when we proposed to him to do something wrong. I do not want to hire someone who will try to do something the wrong way if he knows better one.
我完全不同意Airsource有限公司的说法,他说“不可能”不是面试官想要的回答。在我的面试中,当我遇到一个好候选人的时候,我就会问这样的问题:当我们建议他做错事的时候,他是否能找到正确的论点。我不想雇佣一个人,如果他知道更好的方法,他会尝试用错误的方式去做一些事情。
#18
1
something you can do with perl: http://www.perlmonks.org/?node_id=577368
您可以使用perl做一些事情:http://www.perlmonks.org/?node_id=577368
#19
1
I would explain to the interviewer that the language consisting of palindromes is not a regular language but instead context-free.
我要向面试官解释,由回文组成的语言不是一种常规的语言,而是与上下文无关的。
The regular expression that would match all palindromes would be infinite. Instead I would suggest he restrict himself to either a maximum size of palindromes to accept; or if all palindromes are needed use at minimum some type of NDPA, or just use the simple string reversal/equals technique.
匹配所有回文的正则表达式将是无限的。相反,我建议他把自己限制在一个最大的回文量,以便接受;或者,如果所有的回文都需要使用至少某种类型的NDPA,或者仅仅使用简单的字符串反转/equals技术。
#20
1
The best you can do with regexes, before you run out of capture groups:
在您用完捕获组之前,最好使用regexes:
/(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?).?\9\8\7\6\5\4\3\2\1/
This will match all palindromes up to 19 characters in length.
这将匹配所有的回文长度高达19个字符。
Programatcally solving for all lengths is trivial:
编程地求解所有长度是很简单的:
str == str.reverse ? true : false
#21
1
I don't have the rep to comment inline yet, but the regex provided by MizardX, and modified by Csaba, can be modified further to make it work in PCRE. The only failure I have found is the single-char string, but I can test for that separately.
我还没有代表对内联进行评论,但是MizardX提供并由Csaba修改的regex可以进一步修改,使其在PCRE中工作。我发现的唯一错误是单字符字符串,但是我可以分别测试它。
/^((.)(?1)?\2|.)$/
/ ^((。)(1)? \ 2 |。)/美元
If you can make it fail on any other strings, please comment.
如果您可以使它在任何其他字符串上失败,请评论。
#22
1
#!/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";
#23
1
From automata theory its impossible to match a paliandrome of any lenght ( because that requires infinite amount of memory). But IT IS POSSIBLE to match Paliandromes of Fixed Length. Say its possible to write a regex that matches all paliandromes of length <= 5 or <= 6 etc, but not >=5 etc where upper bound is unclear
从自动机理论来看,不可能匹配任何一种光线(因为那需要无限的内存)的paliandrome。但是有可能匹配固定长度的Paliandromes。假设可以编写一个regex来匹配长度<= 5或<= 6等的所有paliandromes,但不能编写>=5等,其中上限不明确
#24
1
In Ruby you can use \b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z])\b
to match palindrome words such as a, dad, radar, racecar, and redivider
. ps : this regex only matches palindrome words that are an odd number of letters long.
在Ruby中,你可以使用\b(?'word'(?'letter'[a-z])\g' \k'letter '\ +0'|[a-z])\b来匹配palindrome单词,如a、dad、radar、racecar和redivider。ps:这个regex只匹配奇数个字母的回文单词。
Let's see how this regex matches radar. The word boundary \b matches at the start of the string. The regex engine enters the capturing group "word". [a-z] matches r which is then stored in the stack for the capturing group "letter" at recursion level zero. Now the regex engine enters the first recursion of the group "word". (?'letter'[a-z]) matches and captures a at recursion level one. The regex enters the second recursion of the group "word". (?'letter'[a-z]) captures d at recursion level two. During the next two recursions, the group captures a and r at levels three and four. The fifth recursion fails because there are no characters left in the string for [a-z] to match. The regex engine must backtrack.
让我们看看这个regex如何匹配雷达。单词boundary \b在字符串的开头匹配。regex引擎进入捕获组“word”。[a-z]匹配r,然后将其存储在堆栈中,以便捕获组在递归0级的“字母”。现在,regex引擎将进入组“word”的第一个递归。(?“字母”[a-z])匹配并捕获递归一级的a。regex将进入组“word”的第二个递归。(?“字母”[a-z])捕获递归级别为2的d。在接下来的两个递归过程中,组在第3和第4级捕获a和r。第5次递归失败,因为字符串中没有要匹配的字符。regex引擎必须后退。
The regex engine must now try the second alternative inside the group "word". The second [a-z] in the regex matches the final r in the string. The engine now exits from a successful recursion, going one level back up to the third recursion.
regex引擎现在必须尝试组“word”中的第二个选项。regex中的第二个[a-z]匹配字符串中的最后一个r。引擎现在从一个成功的递归中退出,从一层回到第三层递归。
After matching (&word) the engine reaches \k'letter+0'. The backreference fails because the regex engine has already reached the end of the subject string. So it backtracks once more. The second alternative now matches the a. The regex engine exits from the third recursion.
匹配(&word)后,引擎到达\k'字母+0'。因为regex引擎已经到达主题字符串的末尾,所以backreference失败。所以它又回来了。第二个选项现在与a匹配。regex引擎从第三个递归中退出。
The regex engine has again matched (&word) and needs to attempt the backreference again. The backreference specifies +0 or the present level of recursion, which is 2. At this level, the capturing group matched d. The backreference fails because the next character in the string is r. Backtracking again, the second alternative matches d.
regex引擎再次匹配(&word)并需要再次尝试反向引用。backreference指定+0或当前递归级别,即2。在这个级别,捕获组匹配d。由于字符串中的下一个字符是r,所以backreference失败。
Now, \k'letter+0' matches the second a in the string. That's because the regex engine has arrived back at the first recursion during which the capturing group matched the first a. The regex engine exits the first recursion.
现在,k'字母+0'匹配字符串中的第二个a。这是因为regex引擎返回到第一个递归,在此期间捕获组匹配第一个a。
The regex engine is now back outside all recursion. That this level, the capturing group stored r. The backreference can now match the final r in the string. Since the engine is not inside any recursion any more, it proceeds with the remainder of the regex after the group. \b matches at the end of the string. The end of the regex is reached and radar is returned as the overall match.
regex引擎现在回到了所有递归之外。这个级别,捕获组存储了r。反向引用现在可以匹配字符串的最终r。由于该引擎不再属于任何递归,它将继续处理组之后的regex的其余部分。\b在字符串的末尾匹配。到达regex的末端,雷达作为整体匹配返回。
#25
1
here is PL/SQL code which tells whether given string is palindrome or not using regular expressions:
下面是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;
#26
1
Recursive Regular Expressions can do it!
So simple and self-evident algorithm to detect a string that contains a palindrome:
如此简单且自明的算法来检测包含回文的字符串:
(\w)(?:(?R)|\w?)\1
At rexegg.com/regex-recursion the tutorial explains how it works.
在rexegg.com/regex递归中,教程将解释它是如何工作的。
It works fine with any language, here an example adapted from the same source (link) as proof-of-concept, using PHP:
它适用于任何一种语言,这里有一个示例使用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";
}
outputs
输出
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
Comparing
The regular expression ^((\w)(?:(?1)|\w?)\2)$
do the same job, but as yes/not instead "contains".
PS: it is using a definition where "o" is not a palimbrome, "able-elba" hyphened format is not a palindrome, but "ableelba" is. Naming it definition1.
When "o" and "able-elba" are palindrones, naming definition2.
正则表达式^((\ w)(?:(? 1)| \ w ?)\ 2)美元做同样的工作,但随着是的/不是,而不是“包含”。它使用的定义是o不是palimbrome,“健全的elba”连字符格式不是palindrome,而是ableelba。命名它显出。当“o”和“健全的埃尔巴”是palindrone时,命名定义2。
Comparing with another "palindrome regexes",
与另一个“回文正则表达式”相比,
-
^((.)(?:(?1)|.?)\2)$
the base-regex above without\w
restriction, accepting "able-elba".^(()。(?:? 1 |。?)\ 2)美元以上base-regex没有\ w限制,接受“able-elba”。
-
^((.)(?1)?\2|.)$
(@LilDevil) Use definition2 (accepts "o" and "able-elba" so differing also in the recognition of "aaaaa" and "bbbb" strings).^((。)(1)? \ 2 |。)(@LilDevil)使用美元definition2(接受“o”和“able-elba”所以不同也承认“五星级”和“bbbb”字符串)。
-
^((.)(?1)\2|.?)$
(@Markus) not detected "kook" neither "bbbb"^((。)(? 1)\ 2 |。?)美元(@Markus)没有发现“怪人”也没有“bbbb”
-
^((.)(?1)*\2|.?)$
(@Csaba) Use definition2.^((。)(1)* \ 2 |。)(@Csaba)使用definition2美元。
NOTE: to compare you can add more words at $subjects
and a line for each compared regex,
注意:要进行比较,您可以在$subject中添加更多的单词,并为每个比较regex添加一行,
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";
#27
0
A slight refinement of Airsource Ltd's method, in pseudocode:
对Airsource Ltd的方法稍加改进,在伪代码中:
WHILE string.length > 1
IF /(.)(.*)\1/ matches string
string = \2
ELSE
REJECT
ACCEPT
#28
0
You can also do it without using recursion:
你也可以不使用递归:
\A(?:(.)(?=.*?(\1\2?)\z))*?.?\2\z
or to exclude the empty string:
或排除空字符串:
\A(?=.)(?:(.)(?=.*?(\1\2?)\z))*?.?\2\z
Works with Perl, PCRE, Ruby, Java
使用Perl、PCRE、Ruby和Java
演示
#29
0
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";
}
#30
0
\b([a-z])?([a-z])?([a-z])?\2\1\b/gi
\ b([a - z])?([a - z])?([a - z])? 2 \ \ 1 \ b / gi
Matches 5 letter palindromes such as refer and kayak. It does this using (non-greedy) matching of any three letters, followed by the 2nd and 1st matched letters.
匹配5个字母回文,如参考和kayak。它使用(非贪婪)匹配任意三个字母,然后是第二个和第一个匹配的字母。
Link to regex101 site using this
使用此链接到regex101站点