101

それは私が答えることができなかったインタビューの質問でした：

正規表現を使用して文字列が回文であることを確認するにはどうすればよいですか？

ps「与えられた文字列が回文であるかどうかを確認する方法」という質問がすでにあり、さまざまな言語で多くの回答が得られますが、正規表現を使用した回答はありません。

4

32 に答える 32

169

この質問に対する答えは、「それは不可能です」です。より具体的には、インタビュアーは、あなたが計算理論の授業で注意を払っていたかどうか疑問に思っています.

計算理論のクラスで、有限状態機械について学びました。有限ステート マシンは、ノードとエッジで構成されます。各エッジには、有限のアルファベットの文字で注釈が付けられています。1 つ以上のノードが特別な「受け入れ」ノードであり、1 つのノードが「開始」ノードです。各文字が特定の単語から読み取られると、マシン内の特定のエッジをトラバースします。最終的に受け入れ状態になった場合、マシンはその単語を「受け入れた」と言います。

正規表現は常に同等の有限状態マシンに変換できます。つまり、正規表現と同じ単語を受け入れたり拒否したりするものです (現実の世界では、一部の正規表現言語では任意の関数が許可されていますが、これらはカウントされません)。

すべての回文を受け入れる有限状態マシンを構築することは不可能です。この証明は、任意の数のノードを必要とする文字列、つまり文字列を簡単に作成できるという事実に依存しています。

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 文字の回文 (例: レーダー) を検出するものです。

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

したがって、考えられる単語の長さごとに異なる正規表現が必要になるようです。 Python メーリング リストのこの投稿には、その理由 (有限状態オートマトンとポンピング レンマ) に関する詳細が含まれています。

于 2008-10-24T12:22:36.843 に答える
15

あなたがどれだけ自信を持っているかに応じて、私はこの答えを与えるでしょう：

私は正規表現ではそれをしません。正規表現の適切な使用法ではありません。

于 2008-10-24T12:22:13.550 に答える
14

はい、.Net で実行できます。

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

ここで確認できます！素晴らしい投稿です！

于 2010-07-12T04:08:28.597 に答える
9

いくつかの人がすでに言っているように、箱から出してすぐに一般的な回文を検出する単一の正規表現はありませんが、特定の長さまでの回文を検出したい場合は、次のようなものを使用できます

(.?)(.?)(.?)(.?)(.?).?\5\4\3\2\1
于 2009-09-21T08:32:31.347 に答える
8

再帰を使わずにそれを行うこともできます：

\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

デモ

于 2016-11-24T18:32:44.480 に答える
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 に答える
5

Regex Golf の第 5 レベル(A man, a plan)に対する私の回答は次のとおりです。ブラウザの正規表現で最大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 に答える
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

インラインでコメントする担当者はまだいませんが、MizardXによって提供され、Csabaによって変更された正規表現をさらに変更して、PCREで機能させることができます。私が見つけた唯一の失敗は単一文字列ですが、それを個別にテストすることができます。

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

他の文字列で失敗させることができる場合は、コメントしてください。

于 2012-03-09T18:59:56.010 に答える
2

ZCHudsonが指摘したように、回文のセットは通常の言語ではないため、通常の正規表現では回文であるかどうかを判断できません。

Airsource Ltd が「それはあり得ない」というのはインタビュアーが求めているような答えではないと言うとき、私は完全に同意しません。面接中、良い候補者に直面したとき、私が彼に何か間違ったことを提案したとき、彼が正しい議論を見つけることができるかどうかを確認するために、この種の質問をします. より良い方法を知っていれば、間違った方法で何かをしようとする人を雇いたくありません。

于 2008-10-24T13:30:39.390 に答える
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 
#!/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

\b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z])\bRuby では、 などの回文語の照合に使用できますa, dad, radar, racecar, and redivider。ps : この正規表現は、文字数が奇数の回文語にのみ一致します。

この正規表現がレーダーとどのように一致するか見てみましょう。単語境界 \b は、文字列の先頭に一致します。正規表現エンジンは、キャプチャ グループ「単語」に入ります。[az] は、再帰レベル 0 でキャプチャ グループ「letter」のスタックに格納される r に一致します。ここで、正規表現エンジンはグループ「単語」の最初の再帰に入ります。(?'letter'[az]) は、再帰レベル 1 で a に一致してキャプチャします。正規表現は、グループ「単語」の 2 番目の再帰に入ります。(?'letter'[az]) は、再帰レベル 2 で d をキャプチャします。次の 2 回の再帰で、グループはレベル 3 と 4 で a と r をキャプチャします。[az] に一致する文字が文字列に残っていないため、5 番目の再帰は失敗します。正規表現エンジンはバックトラックする必要があります。

正規表現エンジンは、グループ「単語」内で 2 番目の選択肢を試行する必要があります。正規表現の 2 番目の [az] は、文字列の最後の r に一致します。エンジンは成功した再帰を終了し、1 レベル戻って 3 番目の再帰に戻ります。

マッチング (&word) の後、エンジンは \k'letter+0' に到達します。正規表現エンジンが既に対象文字列の末尾に到達しているため、後方参照は失敗します。というわけで、また後戻り。2 番目の選択肢が a に一致するようになりました。正規表現エンジンは 3 回目の再帰から終了します。

正規表現エンジンが再び一致 (&word) したため、後方参照を再試行する必要があります。後方参照は、+0 または現在の再帰レベル (2) を指定します。このレベルでは、キャプチャ グループは d に一致しました。文字列内の次の文字が r であるため、後方参照は失敗します。再びバックトラックすると、2 番目の選択肢は d に一致します。

ここで、\k'letter+0' は文字列の 2 番目の a に一致します。これは、正規表現エンジンが、キャプチャ グループが最初の a に一致した最初の再帰に戻ってきたためです。正規表現エンジンは最初の再帰を終了します。

正規表現エンジンは、すべての再帰の外側に戻りました。このレベルで、捕獲グループはr. 後方参照は、文字列の最後の r と一致するようになりました。エンジンはもはや再帰内にないため、グループの後の正規表現の残りの部分に進みます。\b は文字列の末尾に一致します。正規表現の終わりに到達し、レーダーが全体的な一致として返されます。

于 2014-09-08T10:14:11.083 に答える
2

オートマトンの理論から、任意の長さの回文に一致させることは不可能です (これには無限の量のメモリが必要なため)。しかし、固定長の回文数に一致する可能性があります。長さ <= 5 または <= 6 などのすべての回文に一致する正規表現を作成することは可能ですが、上限が不明な >= 5 などには一致しないとします

于 2013-08-15T18:30:34.643 に答える
2

キャプチャ グループを使い果たす前に、正規表現でできる最善のこと:

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

これは、長さが 19 文字までのすべての回文に一致します。

プログラムですべての長さを解くのは簡単です。

str == str.reverse ? true : false
于 2011-10-30T13:10:36.853 に答える
2

perl でできること: http://www.perlmonks.org/?node_id=577368

于 2008-10-24T20:44:35.830 に答える
0

Airsource Ltd の方法を少し改良した疑似コード:

WHILE string.length > 1
    IF /(.)(.*)\1/ matches string
        string = \2
    ELSE
        REJECT
ACCEPT
于 2009-09-21T08:17:26.487 に答える