私は 200,000 語の辞書と文字セットを持っています。単語のすべての文字がその文字セットに含まれているかどうかを確認するアルゴリズムが必要です。単語を一つ一つ確認するのはとても遅いです。膨大な数の単語を処理するため、これを行うためのデータ構造が必要です。何か案は？ありがとう！
例: 私は一連の文字 {b,g,e,f,t,u,i,t,g,n,c,m,m,w,c,s} を持っています。 」と「バフ」。「big」のすべての文字は元のセットのサブセットであり、「big」は私が望むものですが、「buff」は私が望むものではありません。元のセットには「f」が 1 つしかないためです。これが私がやりたいことです。
これは Scrabble や Boggle のようなものですよね？さて、あなたがしていることは、各単語の文字を並べ替えることによって辞書を事前に生成することです. とwordなりdorwます。次に、これらすべてを Trie データ構造に押し込みます。したがって、Trie では、シーケンスdorwは value を指しますword。
[単語を並べ替えたため、一意性が失われ、並べ替えられた 1 つの単語が複数の異なる単語を指している可能性があることに注意してください。 つまり、Trie はそのデータ ノードにリストまたは配列を格納する必要があります]
後ですべての並べ替え手順を実行せずにすばやく読み込む必要がある場合は、この構造を保存できます。
次に行うことは、入力文字を取得し、それらも並べ替えることです。次に、Trie を再帰的に歩き始めます。現在の文字がトライの既存のパスと一致する場合は、それに従います。未使用のレターを使用できるため、現在のレターをドロップすることもできます。
そして、それはとても簡単です。値を持つ Trie 内のノードに遭遇するときはいつでも、それはそこに到達するために使用した文字から作ることができる単語です。これらの単語を見つけたらリストに追加するだけで、再帰が完了すると、すべての可能な単語が見つかります。
入力に文字が繰り返されている場合は、同じ単語の複数のインスタンスが与えられるのを防ぐために追加のロジックが必要になる場合があります (必要な場合を除きます)。そのロジックは、文字を次の文字に「除外」するステップで呼び出すことができます (繰り返されるすべての文字をスキップするだけです)。
[編集] あなたは反対のことをしたいようです. 上記の私の解決策は、一連の文字から作成できるすべての可能な単語を見つけます。しかし、特定の単語をテストして、使用している一連の文字が許可されているかどうかを確認したいとします。
これは簡単です。
使用可能な文字をヒストグラムとして保存します。つまり、文字ごとに、持っている数字を保存します。次に、テスト ワードの各文字を調べながら、新しいヒストグラムを作成します。ヒストグラム バケットの 1 つが使用可能な文字の値を超えるとすぐに、単語を作成できなくなります。最後までやり遂げれば、言葉をうまく作ることができます。
セットを並べ替え、次に各単語を並べ替えて、「マージ」のような操作を行います
配列を使用してレター セットをマークできます。配列の各要素は文字を表します。文字を要素の位置に変換するには、'a' または 'A' の ASCII コードを減算するだけです。最初の要素は 'a' を表し、2 番目の要素は 'b' というように続きます。そして27日は「あ」。要素値は出現を表します。たとえば、配列 {2, 0, 1, 0, ...} は {a, c, a} のように表します。疑似コードは次のようになります。
単語ごとに
配列を新しい配列にコピーします
単語の各文字に対して
文字の要素位置を取得します: position = letter - 'a'
新しい配列の要素の値を1つ減らす: new_array[position]--
値が負の場合、見つかりませんでした: if array[position] < 0 {return not found;}