私はいくつかの文字と頻度カウントを持っています。そして、私は非常に長い単語リストを持っています (1M と言います)。
私がA-1, B-1, D-1("最大で 1 つA、最大で 1 つB、最大で 1 つD")を"BAD"持っているとします。"RAD"
すべての単語を反復処理して単語内の各文字のカウントを調べる代わりに、それらの文字からどの単語を対数時間などで作成できるかを知ることはできますか?
これらの単語に使用できるデータ構造は何ですか? 試してみませんか？私はそれらを知りません。単語ごとに必要な文字を保存できるのもいいですね。助けてください！
すべての文字を含む単語が必要な場合は、以前にそのようなことを行いました (私のクロスワード チート プログラム、言うのは恥ずかしいことです)。
辞書ファイルを取得して前処理し、次のように各行に文字が並べ替えられ、その後に単語自体が続くようにしました。
aaadkrrv:aardvark
次に、文字がある場合はardvkraaそれを並べ替え、コロンの前にその文字列を含む行を探します。grepO(n) で十分だったので使用しましたが、すべての行をバランスのとれた二分木に簡単に配置して、O(log n) の複雑さを得ることができました。
一部の文字のみを使用する単語を探している場合、それはあまり役に立ちませんが、それがあなたが望んでいたものかどうかは明らかではありません.
あなたの説明からあなたが提示する問題を100％把握できるとは言えませんが、私が見たところ、次のことができます：
単語のリストにインデックスを付けます。たとえば、'B1' は 1 つのインデックスであり、文字 B を 1 つしか含まないか、解決しようとしている問題の要件を満たすエントリのリストが含まれます。同じ行に沿って「A1B1」のような「複合」インデックスを使用することもできます。インデックス作成に費やす時間の予算があれば、かなり深いハッシュを作成できます。26 文字のアルファベットを使用していて、4 文字の組み合わせをハッシュしたい場合、インデックスはわずか 14,950 であり、3 文字の場合はわずか 2,600 です。インデックスはリストの 1 回の繰り返しで作成できるため、作成は直線的です。この段階を過ぎると、ルックアップの大部分が対数になります。私の例では、4 文字の単語の検索は 1 回のフェッチになります。もちろん、