6

文字列配列を指定すると、アナグラムである文字列のすべてのグループが返されます。

私の解決策：

配列内の文字列の単語ごとに、O(m lg m) に並べ替えます。m は単語の平均の長さです。

ハッシュ テーブル < string, list > を作成します。

ソートされた単語をキーとしてハッシュ テーブルに入れ、単語のすべての順列 (O(m!)) も生成し、辞書にある場合は、O(m) を使用して辞書 (プレフィックス ツリー マップ) 内の各順列を検索します。 、 (O(1)) をハッシュ テーブルに入れ、並べ替えられたすべての単語が同じキーでリストに入れられるようにします。

全体で、O(n * m * lg m * m!) 時間と O(n* m!) space 、n は指定された配列のサイズです。

m が非常に大きい場合、効率的ではありません、m! .

より良い解決策はありますか？

ありがとう

4

5 に答える 5

10

単語リストにあるすべての文字を含むアルファベットを定義します。次に、アルファベットの文字ごとに異なる素数が必要です。見つけられる最小のものを使用することをお勧めします。

これにより、次のマッピングが得られます: { a => 2, b => 3, c => 5, d => 7, etc }

次に、整数として表現したい単語の文字を数え、次のように結果の整数を作成します。

擬似コード:

result = 1
for each letter:
....result *= power(prime[letter], count(letter,word)

いくつかの例：

あああ=> 2^4

aabb => 2^2 * 3^2 = bbaa = ババ = ...

等々。

したがって、辞書内の各単語を表す整数が得られ、チェックしたい単語を整数に変換できます。したがって、n が単語リストのサイズで、k が最長の単語のサイズである場合、新しい辞書を作成するのに O(nk)、新しい単語をチェックするのに O(k) かかります。

Hackthissite.com には、次のようなプログラミング上の課題があります。スクランブルされた単語が与えられた場合、辞書を調べて、そのアナグラムが辞書にあるかどうかを確認します。私が答えを借りた問題の効率的な解決策に関する良い記事があり、さらなる最適化についても詳しく説明しています。

于 2011-12-16T19:20:06.900 に答える
2

カウントソートを使用して単語をソートし、O(m) でソートできるようにします。ソート後、単語からキーを生成し、ノード（キー、値）をハッシュテーブルに挿入します。鍵の生成は O(m) で実現できます。

複数の文字列を保持できる動的配列として (key,value) の値を取得できます。すでに存在するキーを挿入するたびに、値配列でキーが生成された元の単語をプッシュするだけです。

したがって、全体的な時間の複雑さ O(mn) ここで、n は単語の総数 (入力のサイズ) です。

また、このリンクには同様の問題の解決策があります-> http://yourbitsandbytes.com/viewtopic.php?f=10&t=42

于 2011-12-16T19:15:21.240 に答える
1

辞書を、それらの文字のすべての単語にマップされた単語のソートされた文字のマッピングに変換し、それを保存します。与えられた単語ごとに並べ替え、マッピングからのアナグラムのリストを出力に追加します。

于 2011-12-16T21:47:01.920 に答える
1 
#include <map>
#include <iostream>
#include <set>
#include <algorithm>

int main () {
  std::string word;
  std::map<std::string, std::set<std::string>> anagrams;
  while(std::cin >> word) {
    std::string sortedWord(word);
    std::sort(sortedWord.begin(), sortedWord.end());
    anagrams[sortedWord].insert(word);
  }
  for(auto& pair : anagrams) {
    for(auto& word : pair.second) {
      std::cout << word << " ";
    }
    std::cout << "\n";
  }
}

私よりもビッグオー分析が得意な人に、複雑さを理解してもらいます。

于 2011-12-16T19:30:00.600 に答える
0

私はあなたがO用語でよりうまくやれるとは思わない

  • 各単語の文字を並べ替える
  • ソートされた単語のリストのソート
  • アナグラムの各セットが連続してグループ化されます。
于 2011-12-16T22:03:22.117 に答える