言葉遊びを書いています。単語を検証するために辞書オブジェクトにアクセスできます。単語と一連の追加文字を含む可能性のあるすべての単語を見つける必要があります。例: 単語が「MEN」で、追加文字のセットが「WALOHTD」であるとします。1.MEND 2.WOMEN 3.MENTAL 4. などの単語を見つける方法が必要です。基本的には、「MEN」と特定の追加文字を含むすべての可能な単語を調べています。
確かに、サブワードを含む最初の単語まで辞書全体をループして、特定の文字の存在をチェックするコードを書くことはできますが、それは最適ではありません。1秒以上かかります。最適な解決策への助けは大歓迎です。レイ
問題は、通常の言語の問題とデータ構造の検索の問題が混在していることです。
最初の側面だけを考えると、正規表現を使用する傾向があります。「追加の文字」を繰り返すことができるかどうかはわかりません。できれば[WALOTHD]*MEN[WALOTHD]*、あなたの場合には十分簡単で、簡単に適応できます。
繰り返すことができない場合は[WALOTHD]{0,7}MEN[WALOTHD]{0,7}、ルールに違反するものから始めて除外することができます (「ALLOTMENT」はその表現に一致しますが、L と T を繰り返します)。
または、より複雑な正規表現を構築することもできますが、より良い表現による利点が、それが何であったかを理解するためのコストを上回るかどうかはわかりません.
辞書の検索とは反対に、DAWGはスペース効率が非常に高く、部分文字列を含む一致を比較的効率的に検索できます。これは、このパズルと完全に一致するわけではありません。心配すべき接頭辞と接尾辞の順列がかなりあるからです。テストがなければ、「追加」から繰り返すことができなければかなり良いことであり、できれば恐ろしいことだと思います. しかし、それは単なる推測です。GADDAG は一見の価値があるかもしれません。DAWG よりも大きくなりますが、この種の検索では高速になる可能性があります (GADDAG は、スクラブル解決で使用されます。これは、ここで発生している問題とほとんど同じです)。