3

iPhoneでこのアプリを作成しようとしています。6文字を指定すると、可能な3〜6文字の英単語がすべて出力されます。私はすでに辞書を持っていますが、その方法を知りたいだけです。

私は周りを検索しましたが、Python のスクラブル ソルバーまたは単語検索グリッド ソリューションしか見つかりませんでした。

力ずくの検索でもいいと思いますが、性能が気になります。コードは必要ありません。アルゴリズムまたはアルゴリズム自体へのリンクは問題ありません。それを取得したら、管理できると思います。

ありがとう！

4

3 に答える 3

1

パフォーマンスが気になる場合は、この方法でうまくいくかもしれません。いくつかの前処理が必要ですが、ほぼ瞬時にアナグラムを検索できます。

  1. String キーを String の List にマップするデータ構造を作成します (私は Java の方が詳しいので、その場合は になりますMap<String,List<String>>)。これにより、辞書が格納されます。

  2. 文字列を受け取り、同じ文字をアルファベット順に出力する関数を定義します。たとえば、次のhelloようになりehlloます。kitchenとなりcehikntます。この関数を次のように呼びます。keyify(word)

  3. 前処理部分は次のとおりです。ディクショナリ内の各項目について、その項目のキー ( keyify(item)) のリストを見つけて、その項目をリストに追加します。

  4. 特定の単語のアナグラムを調べるときはkeyify、その単語のリストを調べてください。たとえば、入力が だった場合、kitchenは にkeyifyなり、マップでそれを調べると、 と、私が忘れていたキッチンの他のアナグラムをcehiknt含むリストが表示されます:Pkitchenchicken

于 2011-07-27T03:20:53.510 に答える
0

この回答を確認してください:アナグラムを生成するアルゴリズム.. Jason Cohen による回答を見てください。6 文字の単語をアルファベット順に並べてから、辞書に目を通し、その単語をアルファベット順に並べて比較します。

于 2011-07-27T03:16:07.607 に答える
0

私は実際に数週間前にこの問題に遭遇しましたが、それを解決する方法を見つけることができる最も効率的な方法は

特定の文字列のすべてのサブセットを見つけました (これには O(2^n) が必要です)

次に、辞書を調べて、サブセットがそのサイズのすべての文字列のすべての文字を「使い果たした」かどうかを確認しました

たとえば、文字列「hetre」と単語「the、there、her」が辞書にある場合、すべてのサブセットを計算できます

{h}{e}{t}{r}{e}{he}{ht}{hr}{he}{thet}{her}{reh}... 「hetre」には 32 のサブセットがあります

次に、これらのサブセットのいずれかが辞書の単語に似ているかどうかを確認します。この場合、reh は her に似ています。これは、her が使用される単語であることを意味します。

これは私が考えることができる最も効率的な方法でした

PowerSetを調べて、文字列を「使い切る」関数を作成する方法を考えてください。

別の方法は、文字列のパワーセットを見つけ出し、すべての順列を見つけることによって力ずくで実行することです。これにより、パフォーマンスが破壊されます。

最初の方法と2番目の方法を使用して15文字を超える文字列を入力し始めるまで、問題は発生しませんでした。7まで問題は発生しませんでした

于 2011-07-27T03:38:01.077 に答える