Wie kann ich mithilfe regulärer Ausdrücke überprüfen, ob eine Zeichenfolge ein Palindrom ist?

93

Das war eine Interviewfrage, die ich nicht beantworten konnte:

Wie kann ich mithilfe regulärer Ausdrücke überprüfen, ob eine Zeichenfolge ein Palindrom ist?

ps Es gibt bereits eine Frage " Wie kann man überprüfen, ob die angegebene Zeichenfolge palindrom ist? ", und es gibt viele Antworten in verschiedenen Sprachen, aber keine Antwort, die reguläre Ausdrücke verwendet.

Degvik
quelle
1
stackoverflow.com/questions/3644266/… kann eine Idee geben.
Prakhar
2
Für heutzutage (2018) und wer nach "dem Palindrom-Regex" sucht, siehe Diskussion über PCRE, das rekursive Muster unterstützt , unter Prakhars Link und meinen rekursiven Regex unten mit Vergleichen .
Peter Krauss

Antworten:

151

Die Antwort auf diese Frage lautet: "Es ist unmöglich". Insbesondere fragt sich der Interviewer, ob Sie in Ihrem Unterricht in Computertheorie aufgepasst haben.

In Ihrem rechentheoretischen Kurs haben Sie etwas über endliche Zustandsmaschinen gelernt. Eine endliche Zustandsmaschine besteht aus Knoten und Kanten. Jede Kante ist mit einem Buchstaben aus einem endlichen Alphabet versehen. Ein oder mehrere Knoten sind spezielle "akzeptierende" Knoten und ein Knoten ist der "Start" -Knoten. Wenn jeder Buchstabe aus einem bestimmten Wort gelesen wird, durchlaufen wir die angegebene Kante in der Maschine. Wenn wir in einem akzeptierenden Zustand enden, sagen wir, dass die Maschine dieses Wort "akzeptiert".

Ein regulärer Ausdruck kann immer in eine äquivalente endliche Zustandsmaschine übersetzt werden. Das heißt, eines, das dieselben Wörter wie der reguläre Ausdruck akzeptiert und ablehnt (in der realen Welt erlauben einige reguläre Ausdruckssprachen beliebige Funktionen, diese zählen nicht).

Es ist unmöglich, eine endliche Zustandsmaschine zu bauen, die alle Palindrome akzeptiert. Der Beweis beruht auf den Tatsachen, dass wir leicht eine Zeichenfolge erstellen können, die eine beliebig große Anzahl von Knoten erfordert, nämlich die Zeichenfolge

a ^ xba ^ x (z. B. aba, aabaa, aaabaaa, aaaabaaaa, ....)

wobei a ^ x x-mal wiederholt wird. Dies erfordert mindestens x Knoten, da wir nach dem Erkennen des 'b' x-mal zurückzählen müssen, um sicherzustellen, dass es sich um ein Palindrom handelt.

Wenn Sie schließlich zur ursprünglichen Frage zurückkehren, können Sie dem Interviewer mitteilen, dass Sie einen regulären Ausdruck schreiben können, der alle Palindrome akzeptiert, die kleiner als eine endliche feste Länge sind. Wenn es jemals eine reale Anwendung gibt, bei der Palindrome identifiziert werden müssen, enthält sie mit ziemlicher Sicherheit keine willkürlich langen Anwendungen. Diese Antwort würde also zeigen, dass Sie theoretische Unmöglichkeiten von realen Anwendungen unterscheiden können. Trotzdem wäre der tatsächliche reguläre Ausdruck ziemlich lang, viel länger als ein gleichwertiges 4-Zeilen-Programm (einfache Übung für den Leser: Schreiben Sie ein Programm, das Palindrome identifiziert).

Jose M Vidal
quelle
5
@SteveMoser In Ruby 1.9.x sind reguläre Ausdrücke nicht mehr regulär (im Sinne der Automatentheorie) und daher ist es möglich, nach Palindromen zu suchen. Palindrome können jedoch nicht mit einem regulären regulären Ausdruck überprüft werden (sinnvoll?).
1
@SteveMoser Es gibt eine gute Beschreibung von Rubys Engine für reguläre Ausdrücke ( >=1.9) hier
@ John richtig, also im Kontext der Frage hat Jose Recht und hqt ist falsch.
Steve Moser
2
In akademischer Hinsicht hat ein regulärer Ausdruck bestimmte Grenzen (definiert ein DFA). In der Realität unterstützen viele Regexp-Engines (hauptsächlich Perl und seine Verwandten) Rückreferenzen, die gegen die akademische Definition verstoßen (NFA oder noch breiter werden). Diese Frage hat also unterschiedliche Antworten, je nachdem, welchen Bezugsrahmen der Fragesteller hatte.
Jiggy
In einem mündlichen Test sollten Sie mit "formalz es ist unmöglich" gehen, aber Sie sollten darauf hinweisen, dass einige Regex-Motoren dies zulassen.
Oliver A.
46

Während die PCRE- Engine rekursive reguläre Ausdrücke unterstützt (siehe die Antwort von Peter Krauss ), können Sie auf der ICU- Engine (wie sie beispielsweise von Apple verwendet wird) keinen regulären Ausdruck verwenden, um dies ohne zusätzlichen Code zu erreichen. Sie müssen so etwas tun:

Dies erkennt jedes Palindrom, erfordert jedoch eine Schleife (die erforderlich ist, da reguläre Ausdrücke nicht zählen können).

$a = "teststring";
while(length $a > 1)
{
   $a =~ /(.)(.*)(.)/;
   die "Not a palindrome: $a" unless $1 eq $3;
   $a = $2;
}
print "Palindrome";
Airsource Ltd.
quelle
4
Gute Antwort. Bei der Frage wurde nicht nach einem einzigen regulären Ausdruck gefragt, der ein Palindrom direkt nach dem Auspacken erkennt. Es wurde lediglich nach einer Methode zum Erkennen von Palindromen gefragt, bei der reguläre Ausdrücke verwendet werden. Herzlichen Glückwunsch zu Ihrer Einsicht, um es so zu sehen.
Stewart
1
Siehe auch das einfachste Matching (ohne String-Manipulation) mit nur einem regulären Ausdruck
Peter Krauss
Danke @PeterKrauss. Ich wusste nicht, dass PCRE eine Rekursion hat. Referenzierte Ihre Antwort.
Airsource Ltd
32

Es ist nicht möglich. Palindrome werden nicht durch eine reguläre Sprache definiert. (Siehe, ich habe etwas in der Computertheorie gelernt)

ZCHudson
quelle
2
Die meisten Engines für reguläre Ausdrücke erfassen mehr als reguläre Sprachen (net kann beispielsweise übereinstimmende Klammern erfassen). Nur Standard-Regexe sind auf reguläre langs beschränkt.
Santiago Palladino
In der Frage wurde jedoch der Begriff "regulärer Ausdruck" verwendet ... daher ist die Antwort von ZCHudson richtig.
paxos1977
2
@austirg: ZCHudsons Antwort ist richtig, aber unvollständig. Reguläre Ausdrücke, die in modernen Programmiersprachen verwendet werden, und reguläre Ausdrücke, die in theoretischen CS-Klassen verwendet werden, sind verschiedene Bestien. Der Begriff ist nur ein historisches Erbe. Siehe stackoverflow.com/questions/233243#235199 und meine Antwort.
JFS
2
@JF Sebastian - da muss ich austirg zustimmen. Wenn der Begriff regulärer Ausdruck ohne eine bestimmte Programmiersprache verwendet wird, gilt die Definition von comp sci. Nicht alle Sprachen, die reguläre Ausdrücke unterstützen, können dies, daher sollten wir nicht davon ausgehen, dass die hier verwendete Sprache dies tut.
Rontologe
@Rontologist: Ich sehe keine Einschränkungen bei der Auswahl der Programmiersprache in der Frage, daher ist jede Sprache erlaubt. Schauen Sie rechts: Was bedeutet "regulärer Ausdruck" in den verwandten Fragen? Werden in einer von ihnen bestimmte Programmiersprachen erwähnt?
JFS
27

Mit Perl Regex:

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

Wie viele betont haben, kann dies jedoch nicht als regulärer Ausdruck angesehen werden, wenn Sie streng sein möchten. Reguläre Ausdrücke unterstützen keine Rekursion.

Markus Jarderot
quelle
Dies funktioniert nicht in PCRE (es stimmt nicht mit "abeba" überein), aber es funktioniert in Perl 5.10
newacct
Du hast recht. PCRE scheint die Rekursion als atomare Gruppe zu behandeln, während Perl das Zurückverfolgen innerhalb der Gruppe erlaubt. Ich glaube nicht, dass es möglich ist, diese Prüfung in PCRE durchzuführen.
Markus Jarderot
1
Überraschenderweise funktioniert nicht für nicht-lateinische Sprachen, zum Beispiel armenische Sprache.
Temujin
3
@Temujin Dies liegt entweder daran, dass Unicode-Zeichen als codierte Bytes übereinstimmen ( /uModifikator hinzufügen ), oder an Kombinatorzeichen. (durch .die \XEscape-Sequenz ersetzen ).
Markus Jarderot
1
Mein Muster funktioniert in PCRE nicht. Es funktioniert in Perl. Ihr Muster schlägt fehl, wenn Teilzeichenfolgen wiederholt werden. Zum Beispiel abababa. Bei Verwendung von PCRE-basierten Regex-Engines ist es nicht möglich, die Rekursion für jede Eingabe zu aktivieren. Casimirs Regex verwendet einen anderen Ansatz, der Iteration und veränderlichen Zustand verwendet, und ist ziemlich faszinierend.
Markus Jarderot
15

Hier ist eine, um 4-Buchstaben-Palindrome (z. B. Tat) für jede Art von Zeichen zu erkennen:

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

Hier ist eine, um Palindrome mit 5 Buchstaben (z. B. Radar) zu erkennen und nur nach Buchstaben zu suchen:

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

Es scheint also, dass wir für jede mögliche Wortlänge einen anderen regulären Ausdruck benötigen. Dieser Beitrag auf einer Python-Mailingliste enthält einige Details zum Grund (Finite State Automata und Pumping Lemma).

ZUM
quelle
14

Je nachdem, wie sicher Sie sind, würde ich folgende Antwort geben:

Ich würde es nicht mit einem regulären Ausdruck tun. Es ist keine angemessene Verwendung regulärer Ausdrücke.

Jon Skeet
quelle
3
Ich würde hoffen, dass Sie etwas mehr Erklärungen geben, um zu zeigen, dass Sie die Einschränkungen von Regex wirklich verstehen. Ihre einfache Antwort könnte als "Ich bin ratlos" verstanden werden.
Scott Wegner
Daher die abhängige Klausel, die er gab.
Will Bickford
13

Ja , Sie können es in .Net tun!

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

Sie können es hier überprüfen ! Es ist ein wunderbarer Beitrag!

kev
quelle
Der springende Punkt bei Regex mit .NET-Geschmack ist, dass sie nicht regelmäßig sind, weil sie keine Automaten mit endlichem Zustand sind. Sie sind nicht wirklich Regex im theoretischen Sinne.
Katze
11

StackOverflow ist voll von Antworten wie "Reguläre Ausdrücke? Nein, sie unterstützen es nicht. Sie können es nicht unterstützen."

Die Wahrheit ist, dass reguläre Ausdrücke nichts mehr mit regulären Grammatiken zu tun haben . Moderne reguläre Ausdrücke verfügen über Funktionen wie Rekursions- und Ausgleichsgruppen, und die Verfügbarkeit ihrer Implementierungen nimmt ständig zu (siehe hier beispielsweise Ruby-Beispiele). Meiner Meinung nach ist es nur kontraproduktiv, an der alten Überzeugung festzuhalten, dass reguläre Ausdrücke in unserem Bereich alles andere als ein Programmierkonzept sind. Anstatt sie für die Wortwahl zu hassen, die nicht mehr am besten geeignet ist, ist es Zeit für uns, Dinge zu akzeptieren und weiterzumachen.

Hier ist ein Zitat von Larry Wall , dem Schöpfer von Perl selbst:

(…) Hat im Allgemeinen mit dem zu tun, was wir als „reguläre Ausdrücke“ bezeichnen, die nur am Rande mit echten regulären Ausdrücken zusammenhängen. Trotzdem ist der Begriff mit den Fähigkeiten unserer Pattern Matching Engines gewachsen, daher werde ich hier nicht versuchen, die sprachliche Notwendigkeit zu bekämpfen. Ich werde sie jedoch im Allgemeinen "Regexes" (oder "Regexen", wenn ich in angelsächsischer Stimmung bin) nennen.

Und hier ist ein Blog-Beitrag von einem der Hauptentwickler von PHP :

Da der Artikel ziemlich lang war, hier eine Zusammenfassung der wichtigsten Punkte:

  • Die von Programmierern verwendeten „regulären Ausdrücke“ haben sehr wenig mit dem ursprünglichen Begriff der Regelmäßigkeit im Kontext der formalen Sprachtheorie zu tun.
  • Reguläre Ausdrücke (mindestens PCRE) können mit allen kontextfreien Sprachen übereinstimmen. Als solche können sie auch mit wohlgeformtem HTML und so ziemlich allen anderen Programmiersprachen übereinstimmen.
  • Reguläre Ausdrücke können mit mindestens einigen kontextsensitiven Sprachen übereinstimmen.
  • Die Übereinstimmung regulärer Ausdrücke ist NP-vollständig. Als solches können Sie jedes andere NP-Problem mit regulären Ausdrücken lösen.

Davon abgesehen können Sie Palindrome mit regulären Ausdrücken abgleichen:

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

... was offensichtlich nichts mit regulären Grammatiken zu tun hat.
Weitere Informationen hier: http://www.regular-expressions.info/balancing.html

rr-
quelle
9

Wie einige bereits gesagt haben, gibt es keinen einzigen regulären Ausdruck, der ein allgemeines Palindrom sofort erkennt. Wenn Sie jedoch Palindrome bis zu einer bestimmten Länge erkennen möchten, können Sie so etwas wie verwenden

(.?)(.?)(.?)(.?)(.?).?\5\4\3\2\1
Stewart
quelle
7

Dies kann jetzt in Perl erfolgen. Rekursive Referenz verwenden:

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

geändert basierend auf dem letzten Teil http://perldoc.perl.org/perlretut.html

Hui Liu
quelle
6

In Ruby können Sie benannte Erfassungsgruppen verwenden. so etwas wird funktionieren -

def palindrome?(string)
  $1 if string =~ /\A(?<p>| \w | (?: (?<l>\w) \g<p> \k<l+0> ))\z/x
end

Probieren Sie es aus, es funktioniert ...

1.9.2p290 :017 > palindrome?("racecar")
 => "racecar" 
1.9.2p290 :018 > palindrome?("kayak")
 => "kayak" 
1.9.2p290 :019 > palindrome?("woahitworks!")
 => nil 
Taylor
quelle
1
Benannte Erfassungsgruppen sind nicht ausschließlich Regex. willamette.edu/~fruehr/LLC/lab5.html
Steve Moser
2
Du hast Recht. Aus diesem Grund habe ich darauf hingewiesen, dass Sie benannte Erfassungsgruppen verwenden müssen.
Taylor
Könnte jemand zufällig diesen RE Charakter für Charakter für einen Neuling erklären? Ich verstehe alle folgenden Punkte (Kommas trennen die 'Atome') /, \ A, (, |, \ w, |, (, (, \ w,),),), \ z, /, x, aber ich ziehe an Verstehe ich keine dieser? <p>,?:,? <l>, \ g <p>, \ k <l + 0> und ich benutze rubular.com als Hilfe und es scheint die RE zu verstehen ( natürlich), aber das hilft mir nicht, es zu sehen, und sogar "Eine vollständige Ruby-Regex-Anleitung finden Sie in der Spitzhacke." hilft nicht, denn die mit 'Pickaxe' verknüpfte Seite erklärt nicht die Atome, die ich nicht verstehe. Ich weiß ? FOLGENDE Übereinstimmungen Null oder eine von a, aber? vor einem Charakter?
Kevin Ford der U-Bootfahrer
Ah, benannte Eroberungsgruppen ! Nett. @SteveMoser, das ist jetzt ein defekter Link, aber ich habe einen anderen gefunden . Vielen Dank an Taylor für die Erwähnung, da ich sonst keine Ahnung gehabt hätte, was mit? <P> und? <L> und ?: (Nicht erfassende Erfassungsgruppe) und \ g <p> und \ k <l + gemeint ist 0>. Ich kann immer noch nicht sehen, was? <P> | ist aber. Nicht | bedeuten "oder"? Ich kann keine Dokumentation dieser Verwendung für die Pipe in REs finden. Ich würde mich immer noch freuen, eine detaillierte Erklärung für diesen sehr schönen RE zu sehen.
Kevin Ford der U-Bootfahrer
5

Es ist tatsächlich einfacher, dies mit der Manipulation von Zeichenfolgen zu tun, als mit regulären Ausdrücken:

bool isPalindrome(String s1)

{

    String s2 = s1.reverse;

    return s2 == s1;
}

Mir ist klar, dass dies die Interviewfrage nicht wirklich beantwortet, aber Sie könnten damit zeigen, wie Sie eine Aufgabe besser erledigen können, und Sie sind nicht die typische Person mit einem Hammer, die jedes Problem als Nagel ansieht . "

Dan
quelle
Obwohl ich diese Antwort sehr mag, denke ich, dass Sie zusätzliche Punkte erhalten, wenn Sie BreakIterator verwenden, um die Zeichenfolge ordnungsgemäß in visuelle Zeichen aufzuteilen.
Trejkaz
5

Hier ist meine Antwort auf Regex Golfs 5. Level (Ein Mann, ein Plan). Es funktioniert mit Regexp des Browsers für bis zu 7 Zeichen (ich verwende Chrome 36.0.1985.143).

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

Hier ist eine für bis zu 9 Zeichen

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

Um die maximale Anzahl von Zeichen zu erhöhen, für die es funktionieren würde, würden Sie wiederholt ersetzen . mit (?: (.).? \ n?)? .

pbatey
quelle
1
Ich habe das mit etwas weniger Zeichen geschafft, ^ (.) (.) (.)?.? \ 3 \ 2 \ 1 $
Ben Ellis
Vielen Dank, dass du es mir verdorben hast :-)
U10-Forward
Warum der Rest der Leute 13 hat, aber das ist 19
U10-Forward
5

Rekursive reguläre Ausdrücke können es tun!

So einfacher und selbstverständlicher Algorithmus, um eine Zeichenfolge zu erkennen, die ein Palindrom enthält:

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

Unter rexegg.com/regex-recursion erklärt das Tutorial, wie es funktioniert.


Es funktioniert gut mit jeder Sprache, hier ein Beispiel aus derselben Quelle (Link) wie Proof-of-Concept mit 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";
}

Ausgänge

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

Vergleichen

Der reguläre Ausdruck ^((\w)(?:(?1)|\w?)\2)$ erledigt den gleichen Job, aber als yes / not "enthält".
PS: Es wird eine Definition verwendet, bei der "o" kein Palimrom ist, das Bindestrich-Format "able-elba" kein Palindrom ist, "ableelba" jedoch. Benennung es definition1 .
Wenn "o" und "able-elba" Palindronen sind, benennen Sie definition2 .

Vergleich mit anderen "Palindrom-Regexen",

  • ^((.)(?:(?1)|.?)\2)$die Basis-Regex oben ohne \wEinschränkung, akzeptiert "able-elba".

  • ^((.)(?1)?\2|.)$( @LilDevil ) Verwenden Sie definition2 (akzeptiert "o" und "able-elba", die sich auch in der Erkennung von "aaaaa" - und "bbbb" -Strings unterscheiden).

  • ^((.)(?1)\2|.?)$( @Markus ) weder "kook" noch "bbbb" erkannt

  • ^((.)(?1)*\2|.?)$( @Csaba ) Verwenden Sie definition2 .


HINWEIS: Zum Vergleichen können Sie $subjectsfür jeden verglichenen regulären Ausdruck mehr Wörter und eine Zeile hinzufügen.

  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
quelle
5

Sie können dies auch ohne Rekursion tun:

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

um ein einzelnes Zeichen zuzulassen:

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

Funktioniert mit Perl, PCRE

Demo

Für Java:

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

Demo

Casimir et Hippolyte
quelle
1
Dies ist eine sehr interessante Antwort auf eine Regex-Frage. Eigentlich das einzige Muster, das einige meiner Tests bestanden hat . Vielen Dank für diesen einen Casimir :)
Bobble Bubble
1
@ Bobblebubble: Danke für deine Unterstützung. Wie Sie sehen können, habe ich diese Antwort kürzlich bearbeitet, weil die vorherige Version falsch war (drei Jahre lang, was für eine Schande).
Casimir et Hippolyte
4

In Bezug auf den PCRE-Ausdruck (von MizardX):

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

Hast du es getestet? Auf meinem PHP 5.3 unter Win XP Pro schlägt dies fehl: aaaba Eigentlich habe ich den Ausdruck Ausdruck leicht geändert, um zu lesen:

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

Ich denke, was passiert ist, dass das äußere Zeichenpaar zwar verankert ist, die übrigen jedoch nicht. Dies ist nicht ganz die ganze Antwort, denn während "aaaba" und "aabaacaa" fälschlicherweise weitergegeben werden, schlägt es bei "aabaaca" korrekt fehl.

Ich frage mich, ob es eine Lösung dafür gibt und ob das Perl-Beispiel (von JF Sebastian / Zsolt) meine Tests korrekt besteht.

Csaba Gabor aus Wien


quelle
3

In Perl (siehe auch Zsolt Botykais Antwort ):

$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
quelle
2

Wie von ZCHudson hervorgehoben , kann festgestellt werden, ob etwas ein Palindrom ist, das nicht mit einem üblichen regulären Ausdruck ausgeführt werden kann, da der Palindromsatz keine reguläre Sprache ist.

Ich bin völlig anderer Meinung als Airsource Ltd, wenn er sagt, dass "es nicht möglich ist" nicht die Art von Antwort ist, nach der der Interviewer sucht. Während meines Interviews komme ich zu dieser Art von Frage, wenn ich einem guten Kandidaten gegenüberstehe, um zu prüfen, ob er das richtige Argument finden kann, als wir ihm vorgeschlagen haben, etwas falsch zu machen. Ich möchte niemanden einstellen, der versucht, etwas falsch zu machen, wenn er es besser kennt.

Nicolas
quelle
2

Ich würde dem Interviewer erklären, dass die aus Palindromen bestehende Sprache keine reguläre Sprache ist, sondern kontextfrei.

Der reguläre Ausdruck, der zu allen Palindromen passen würde, wäre unendlich . Stattdessen würde ich vorschlagen, dass er sich entweder auf eine maximale Größe von Palindromen beschränkt, um sie zu akzeptieren; oder wenn alle Palindrome benötigt werden, verwenden Sie mindestens eine Art von NDPA oder verwenden Sie einfach die einfache String-Umkehr- / Gleichheitstechnik.

Flamme
quelle
2

Das Beste, was Sie mit regulären Ausdrücken tun können, bevor Ihnen die Erfassungsgruppen ausgehen:

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

Dies entspricht allen Palindromen mit einer Länge von bis zu 19 Zeichen.

Das programmgesteuerte Lösen für alle Längen ist trivial:

str == str.reverse ? true : false
Chris
quelle
Ihre Regex funktioniert nicht. Zum Beispiel wird es anzeigen, dass "abac" ein Match ist ...
Darwin Airola
2

Ich habe noch nicht den Repräsentanten, um Inline-Kommentare abzugeben, aber der von MizardX bereitgestellte und von Csaba geänderte Regex kann weiter geändert werden, damit er in PCRE funktioniert. Der einzige Fehler, den ich gefunden habe, ist die Zeichenfolge mit einem Zeichen, aber ich kann das separat testen.

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

Wenn Sie es bei anderen Zeichenfolgen zum Scheitern bringen können, kommentieren Sie dies bitte.

Lil Devil
quelle
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";
Sapam
quelle
2

Aus der Automatentheorie ist es unmöglich, ein Paliandrom beliebiger Länge zu finden (da dies unendlich viel Speicher erfordert). Es ist jedoch möglich, Paliandrome mit fester Länge anzupassen. Angenommen, es ist möglich, einen regulären Ausdruck zu schreiben, der allen Paliandromen der Länge <= 5 oder <= 6 usw. entspricht, jedoch nicht> = 5 usw., wenn die Obergrenze unklar ist

Vijeenrosh PW
quelle
2

In Ruby können Sie \b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z])\bpalindrome Wörter wie z a, dad, radar, racecar, and redivider. ps: Dieser reguläre Ausdruck stimmt nur mit palindromen Wörtern überein, die eine ungerade Anzahl von Buchstaben lang sind.

Mal sehen, wie dieser Regex zum Radar passt. Die Wortgrenze \ b stimmt am Anfang der Zeichenfolge überein. Die Regex-Engine gibt die Erfassungsgruppe "Wort" ein. [az] stimmt mit r überein, das dann im Stapel für die Erfassungsgruppe "Buchstabe" auf der Rekursionsstufe Null gespeichert wird. Jetzt gibt die Regex-Engine die erste Rekursion der Gruppe "Wort" ein. (? 'letter' [az]) stimmt mit einem auf Rekursionsstufe 1 überein und erfasst es. Der Regex gibt die zweite Rekursion der Gruppe "Wort" ein. (? 'Buchstabe' [az]) erfasst d auf Rekursionsstufe zwei. Während der nächsten zwei Rekursionen erfasst die Gruppe a und r auf den Ebenen drei und vier. Die fünfte Rekursion schlägt fehl, da in der Zeichenfolge keine Zeichen mehr vorhanden sind, damit [az] übereinstimmt. Die Regex-Engine muss zurückverfolgen.

Die Regex-Engine muss nun die zweite Alternative innerhalb der Gruppe "Wort" ausprobieren. Das zweite [az] in der Regex entspricht dem letzten r in der Zeichenfolge. Die Engine verlässt nun eine erfolgreiche Rekursion und geht eine Ebene zurück bis zur dritten Rekursion.

Nach dem Abgleich (& Wort) erreicht die Engine \ k'letter + 0 '. Die Rückreferenz schlägt fehl, weil die Regex-Engine bereits das Ende der Betreffzeichenfolge erreicht hat. Also zieht es sich wieder zurück. Die zweite Alternative entspricht jetzt der a. Die Regex-Engine verlässt die dritte Rekursion.

Die Regex-Engine hat erneut eine Übereinstimmung (& word) und muss die Rückreferenz erneut versuchen. Die Rückreferenz gibt +0 oder die aktuelle Rekursionsstufe an, die 2 ist. Auf dieser Stufe stimmte die Erfassungsgruppe mit d überein. Die Rückreferenz schlägt fehl, weil das nächste Zeichen in der Zeichenfolge r ist. Beim zweiten Zurückverfolgen entspricht die zweite Alternative d.

Jetzt stimmt \ k'letter + 0 'mit dem zweiten a in der Zeichenfolge überein. Dies liegt daran, dass die Regex-Engine bei der ersten Rekursion angekommen ist, bei der die Erfassungsgruppe mit der ersten a übereinstimmte. Die Regex-Engine verlässt die erste Rekursion.

Die Regex-Engine ist jetzt wieder außerhalb aller Rekursionen. Dass diese Ebene die Erfassungsgruppe r gespeichert. Die Rückreferenz kann jetzt mit dem letzten r in der Zeichenfolge übereinstimmen. Da sich die Engine nicht mehr in einer Rekursion befindet, wird der Rest des regulären Ausdrucks nach der Gruppe fortgesetzt. \ b stimmt mit dem Ende der Zeichenfolge überein. Das Ende der Regex ist erreicht und das Radar wird als Gesamtspiel zurückgegeben.

Melih Altıntaş
quelle
2

Hier ist PL / SQL-Code, der anhand regulärer Ausdrücke angibt, ob eine bestimmte Zeichenfolge palindrom ist oder nicht:

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
quelle
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";
}
Kanchan Sen Laskar
quelle
2
Während dieser Code die Frage beantworten kann, würde die Bereitstellung eines zusätzlichen Kontexts darüber, wie und / oder warum er das Problem löst, den langfristigen Wert der Antwort verbessern.
Donald Duck
2

Diese Regex erkennt Palindrome mit bis zu 22 Zeichen, wobei Leerzeichen, Tabulatoren, Kommas und Anführungszeichen ignoriert werden.

\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

Spielen Sie hier damit: https://regexr.com/4tmui

Tony Tonev
quelle
0

Eine leichte Verfeinerung der Methode von Airsource Ltd im Pseudocode:

WHILE string.length > 1
    IF /(.)(.*)\1/ matches string
        string = \2
    ELSE
        REJECT
ACCEPT
Stewart
quelle