8

これはインタビューの質問です：

文字列を指定して、辞書内の単語であるすべての順列を見つけます。

私の解決策：

辞書のすべての単語を接尾辞木に入れてから、ツリー内の文字列の各順列を検索します。

検索時間はO(n)、です。ここnで、は文字列のサイズです。ただし、文字列にはn!順列がある場合があります。

どうすれば効率を改善できますか？

4

6 に答える 6

9

あなたの一般的なアプローチは悪くありません。

ただし、すべての文字がアルファベット順になるように単語を再配置してから、各単語が同様にアルファベット順に再配置されて元の単語にマッピングされる辞書を検索することで、各順列を検索する必要をなくすことができます。

それをそのまま把握するのは少し難しいかもしれないと思いますので、ここに例を示します。あなたの言葉が飛躍しているとしましょう。これをaelpに再配置します。

今あなたの辞書にあなたは「罪状認否」と「淡い」という言葉を持っているかもしれません。提案どおりに実行すると、辞書には（とりわけ）次のマッピングが含まれます。

...
aelp -> pale
aelp -> plea
...

したがって、アナグラムを見つけるには、4つすべてではなく、aelpのエントリを見つけるだけで済みます（たとえば、提案されている接尾辞木アプローチを使用）。=飛躍の24の順列。

于 2011-12-08T04:46:12.880 に答える
2

迅速な代替ソリューション-すべては、問題のデータ構造のサイズによって異なります。

辞書が適度に小さく、文字列が適度に長い場合は、辞書の各エントリを調べて、それらが文字列の順列であるかどうかを判断できます。あなたはより賢くなります-あなたは辞書をソートして特定のエントリをスキップすることができます。

于 2011-12-08T04:38:36.707 に答える
1

ソートされた文字のリストから単語のリストへのマップを作成できます。

たとえば、次のようになります。

Array (him, hip, his, hit, hob, hoc, hod, hoe, hog, hon, hop, hos, hot)

それらを内部で並べ替えます。

 Array (him, hip, his, hit, bho, cho, dho, eho, gho, hno, hop, hos, hot)

結果を並べ替えます。

 Array (bho, cho, dho, eho, gho, him, hip, his, hit, hno, hop, hos, hot)

この小さなサンプルでは、​​一致するものはありませんが、特定の単語については、内部で並べ替え、これをキーとしてマップを調べます。

于 2011-12-08T04:49:21.360 に答える
1

辞書の単語を保存するためにハッシュマップを使用してみませんか？したがって、O（1）ルックアップ時間が得られます。また、入力が英語の場合は、別のテーブルを作成して辞書内のすべての可能な文字を伝えることができます。このテーブルを使用して、最初にいくつかの入力をフィルタリングできます。次に例を示します。

result_list = empty;   

for(char in input)
{
   if(char not in letter_table)
   {
      return result_list;
   }
}

for(entry in permutations of input)
{
    if(entry in dictionary_hash_table)
    { 
        result_list->add_entry();
    }
}

return result_list
于 2011-12-08T05:07:18.617 に答える
1

あなたは言葉をトライに入れるべきです。次に、順列を生成するときに単語を検索できます。最初の部分がトライにない場合は、順列のブロック全体をスキップできます。

http://en.wikipedia.org/wiki/Trie

于 2011-12-08T17:37:32.457 に答える
0

別の簡単な解決策は、以下のアルゴリズムのようになります。

1）「next_permutation」を使用して、一意の順列を見つけます。

2）「find / find_if」を使用して、辞書に対して検索します。

于 2011-12-08T06:48:27.327 に答える