0

特定の文字セットのすべての可能なアナグラムをリストするために、この正規表現を拡張しようとしています。

^(?!.*([aer]).*\1)(?!(.*d){4})([aerd]*|[a-z])$

これまでのところ、この正規表現に基づいて、「adder」、「add」、「ad」、「red」など、「dadder」という文字で構成される単語とサブワードの任意の組み合わせで一致を受け取ることができます。単純ではなく正規表現の複雑さの理由[dadder]*は、明らかに各文字が無限に一致する可能性があるためです。これは悪いことです。各文字をテスト文字列に1回だけ一致させたいのですが、2つのdが指定されている場合、最大で一致する可能性がありますわずか2回以下。もちろん、誰かが正規表現を合理化して、指定された文字の組み合わせを正確にX回一致させることができる場合は、お気軽に提供してください:)

ただし、私の主な質問は、ピリオド文字「.」を組み込みたいと思います。文字のリストで終止符が見つかった場合、それはワイルドカードとして機能し、任意の文字 a ～ z と一致する可能性があります。、、などと一致dadd.rする可能性があります。daddzrdaddordaddprrpdadd

誰でもこれで私を助けることができますか？

4

3 に答える 3

1

nhahtdh の面白い答えがあなたを納得させるはずなので、これは正規表現で解決すべき問題ではありません。

正規表現は、パターンのマッチングに優れています。それらは、セットベースの問題を解決するためのツールではありません。これは、それらを使用しようとしている目的です。

それが問題の性質であるため、アルゴリズムのアプローチが本当に必要です。 この質問はまさにそのようなトピックをカバーしています。

于 2013-03-01T11:39:57.620 に答える
1

質問の最初の部分は、この質問の複製です:文字列が一連の文字のサブセットであるかどうかを確認しますか? (正規表現)?

この回答は、直面している実際の問題 (質問の 2 番目の部分) に取り組むことに専念しています。

非常に単純な解決策は、2 つのマップを使用することです。1 つは元のセットの文字の頻度をマップし、 の数を記録し.、もう 1 つは各入力文字列の文字の頻度をマップします。

擬似コード:

// I assume the maps return 0 for non existent entries
// Depending on the input, the map can simply be an array, or a tree/hash map

function checkAnagramExtended(originalString, inputString):
    if (inputString.length > originalString.length):
        return false

    // The frequency mapping for original string (ref stands for reference)
    // Ideally, refMap should be filled up once instead of every call
    // to this function
    var refMap = countFrequency(originalString)
    // The frequency mapping for input string
    var inpMap = empty map

    foreach (character c in inputString):

        if (inpMap[c] >= refMap[c]):
            // You may want to check that c is a character allowed
            // to be substituted by dot .
            // if (!canBeSubstitutedByDot(c)):
            //     return false

            if (inpMap['.'] >= refMap['.']):
                return false
            else:
                inpMap['.'] += 1

        else:
            inpMap[c] += 1

    return true

付録: 正規表現ソリューションの拡張?

任意の文字を一致させることができるドット.拡張a-zにより、正規表現ソリューションはさらに非現実的になります。

もう 1 つの問題に対する私の解決策では、否定先読みに大きく依存して、特定の文字の数が文字のマルチセット内の最大文字数よりも少ないことを確認しました。

ドット.拡張子は、任意の文字に許可される最大文字数を変えることができるため、上記の私の解決策を破ります。正規表現に仕事を強制すると、 1 しかない場合でも正規表現を生成でき.ますが、2 に増やすと事態は爆発します。

于 2013-03-01T12:15:23.087 に答える
0

さて、これを正規表現として実行しようと多くの労力を費やした後、ワイルドカードのサポートが不完全で処理時間が遅いため、私は諦めました。

要件をC＃関数に変換しました。これは、約400％高速であるため、実際にははるかに快適で幸せです。

これにより、指定された単語が、（。）を介してワイルドカードをサポートする一連の文字のアナグラムまたはサブアナグラムであるかどうかがチェックされます。

lettersアナグラムをテストするための文字はどこにありますか。

テストする単語dictionaryDataはどこにありますか。List<string>

var letterCounts = letters.Select(x => x)
  .GroupBy(x => x)
  .ToDictionary(x => x.Key, x => x.Count());

var containsWildcards = letters.IndexOf('.') >= 0;
foreach (var dictWord in dictionaryData)
{
    var matches = 0;
    var dictWordLength = dictWord.Length;
    if (dictWordLength > letters.Length)
        continue;
    var addedChars = new List<char>();
    foreach (var dictLetter in dictWord)
    {
        var foundLetter = false;
        if (letterCounts.ContainsKey(dictLetter) &&
            addedChars.Count(x => x == dictLetter) < letterCounts[dictLetter])
        {
            if (letters.IndexOf(dictLetter) >= 0)
                foundLetter = true;
        }
        else if (containsWildcards &&
            addedChars.Count(x => x == '.') < letterCounts['.'])
        {
            addedChars.Add('.');
            foundLetter = true;
        }
        if (foundLetter)
        {
            addedChars.Add(dictLetter);
            matches++;
        }
        if (dictWordLength == matches)
            break;
    }

    if (dictWordLength <= matches)
    {
        // We have a match!
    }
}

それが他の誰かにも役立つことを願っています。

于 2013-03-01T14:25:26.147 に答える