1

少し問題があります。たとえば「abcdaefg」のように8文字で、たとえば「ママ」、「パパ」、「悪い」、「たばこ」、「abac」などの単語のリストがあります。

私が持っている文字でこれらの単語を構成できるかどうかを確認するにはどうすればよいですか？私の例では、bad、abac、fagを作成できますが、お父さん（Dが2つない）とお母さん（MまたはOがない）を作成することはできません。

正規表現を使用して実行できると確信していますが、Perlの一部の関数を使用しても役立つでしょう。よろしくお願いします。:)

4

6 に答える 6

6

これは、テストする単語から正規表現を作成することによって最も簡単に実行できます。

これにより、使用可能な文字のリストがソートされ、それらを連結して文字列が形成されます。次に、各候補単語が文字に分割され、並べ替えられ、正規表現用語.*を区切り文字として再結合されます。したがって、たとえばabacは に変換されa.*a.*b.*cます。

次に、派生した正規表現に対して使用可能な文字列をテストすることにより、単語の有効性が判断されます。

use strict;
use warnings;

my @chars = qw/ a b c d a e f g /;
my $chars = join '', sort @chars;

for my $word (qw/ mom dad bad fag abac /) {
  my $re = join '.*', sort $word =~ /./g;
  print "$word is ", $chars =~ /$re/ ? 'valid' : 'NOT valid', "\n";
}

出力

mom is NOT valid
dad is NOT valid
bad is valid
fag is valid
abac is valid
于 2013-01-17T16:59:16.680 に答える
3

これは、正規表現の方法を支持するのではなく、可能性を実証するためのものです。他の健全な解決策を検討してください。

最初のステップとして、使用可能な文字数を数えます。

次に、正規表現をそのように構築します (これは Perl コードではありません! ):

入力アンカーの先頭から開始します。これは、文字列の先頭 (リストからの 1 つの単語) と一致します。

^

これらを一意の文字の数だけ追加します。

(?!(?:[^<char>]*+<char>){<count + 1>})

例:(?!(?:[^a]*+a){3})の数aが 2 の場合。

ここでは、 zero-width negative look-ahead と呼ばれる高度な正規表現構造を使用しました(?!pattern)。テキストを消費せず、指定されたパターンと一致する文字列が先にないことを確認するために最善を尽くします(?:[^a]*+a){3}。基本的には、文字列で 3 'a' が先に見つからないことを確認するという考え方です。本当に「a」が 3 つ見つからない場合は、文字列に含まれる「a」が 2 つ以下であることを意味します。

*+0 以上の量指定子である を所有格として使用していることに注意してください。これは、不要な後戻りを避けるためです。

内に表示できる文字を入力してください[]:

[<unique_chars_in_list>]+

例： の場合a b c d a e f g、 になり[abcdefg]+ます。この部分は実際に文字列を消費し、文字列にリスト内の文字のみが含まれていることを確認します。

文字列の末尾に一致する入力アンカーの末尾で終了します。

$

したがって、あなたの例では、正規表現は次のようになります。

^(?!(?:[^a]*+a){3})(?!(?:[^b]*+b){2})(?!(?:[^c]*+c){2})(?!(?:[^d]*+d){2})(?!(?:[^e]*+e){2})(?!(?:[^f]*+f){2})(?!(?:[^g]*+g){2})[abcdefg]+$

i大文字と小文字を区別しない一致のフラグも指定する必要があります。

これは、一致する単語のリストで英語のアルファベット (az) のケースのみを考慮することに注意してください。スペースとハイフンは (まだ) ここでは考慮されていません。

于 2013-01-17T16:22:19.170 に答える
1

両方の文字列をアルファベット順に並べ替えてから、チェックしたい文字列について、次のように各文字の間に .* を挿入してください。

'aabcdefg' =~ m/a.*b.*d.*/
True
'aabcdefg' =~ m/m.*m.*u.*/
False
'aabcdefg' =~ m/a.*d.*d.*/
False
于 2013-01-17T16:54:19.780 に答える
0

いくつかの擬似コード：

  • 使用可能な文字をアルファベット順に並べ替えます

  • 単語ごとに：

    • 単語の文字をアルファベット順に並べ替えます
      • 単語検索の各文字について、使用可能な文字を前方に検索して、一致する文字を見つけます。この検索で​​は、使用可能な文字の先頭に戻ることはなく、一致した文字が消費されることに注意してください。

またはさらに良いことに、文字の頻度カウントを使用します。使用可能なキャラクターについて、キャラクターからそのキャラクターの出現回数までのマップを作成します。各候補単語について同じことを行い、利用可能なマップと比較します。単語マップに利用可能なマップが含まれていない文字のマッピングが含まれている場合、またはマップされた値が利用可能なマップよりも単語マップで大きい場合、その単語はできません。使用可能な文字を使用して構築されます。

于 2013-01-17T16:25:08.530 に答える
0

これは、一般化するのがかなり簡単な非常に単純なスクリプトです。

#!/usr/bin/env perl

use strict;
use warnings;

sub check_word {
  my $word = shift;
  my %chars;
  $chars{$_}++ for @_;
  $chars{$_}-- or return for split //, $word;
  return 1;
}

print check_word( 'cab', qw/a b c/ ) ? "Good" : "Bad";

そしてもちろん、文字リストが毎回同じになる場合、この関数のパフォーマンスは大幅に向上する可能性があります。実際には 8 文字の場合、ハッシュをコピーするのと毎回新しいハッシュを作成するのは、おそらく同じ速度です。

于 2013-01-17T22:52:09.887 に答える
-2

擬似コード：

bool possible=true
string[] chars= { "a", "b", "c"}   
foreach word in words
{
     foreach char in word.chars
     {
          possible=possible && chars.contains(char)
     }
}
于 2013-01-17T16:12:28.380 に答える