2

単語の配列を指定して、アナグラムをグループ化 IP:{tar,rat,banana,atr} OP:{[tar,rat,atr],[banana]}

ハッシュ テーブルを使用して、この質問に対する 1 つの解決策を示します。各単語を検討し、並べ替えて、存在しない場合はハッシュ テーブルにキーとして追加します。キーの値は、同じキーを持つすべてのアナグラムのリストになります。時間の複雑さについて知りたかったのですが、配列内の文字を並べ替えるには、O(n log n) と仮定します。ハッシュ テーブルに格納するには、O(n)、合計 O(n*nlogn) になります。

より良いアルゴリズムはありますか？時間の複雑さが少ないですか？

4

1 に答える 1

1

時間の複雑さのために、カウントソートを使用して個々の単語を並べ替えることができますが、これには単語ごとに線形の時間がかかります。また、最初に文字の出現回数をカウントしてから、並べ替えられた単語の代わりに出現回数をハッシュすることもできます。これは、並べ替えをカウントして再構築ステップを差し引いたものと本質的に同じです。

しかし、言葉は通常短いので、これは実用的な利点をもたらさないかもしれません.

于 2013-07-29T21:42:18.207 に答える