以下は、あるインタビューで私に尋ねられた質問です。私たちは食べるのアナグラムを知っています: お茶と食べた. 問題は: 私たちはプログラムを持っています. このプログラムに 1 万個のアルファベットのリストをフィードします。プログラムを実行します。実行時に、このプログラムに単語を提供します。"eat" これで、プログラムは 10,000 個のアルファベットのリストに存在するアナグラムの数を返すはずです。したがって、「食べる」の入力に対しては、2 を返す必要があります。
アナグラムの数を簡単に見つけられるように、これらの 10,000 個のアルファベットを格納する戦略は何でしょうか。
各単語の文字を順序付けを最小化するように並べます。つまり、 にteaなりaetます。
次に、これらを単語からカウントへの（ハッシュ）マップに入れるだけです（ と の両方teaが にateマップされるaetため、マップに含ま(aet, 2)れます）
次に、単語を取得したら、上記のように文字を並べ替えて、カウントのルックアップを行います。
実行時間：
リスト内の単語を想定するnと、平均単語長はm...
予想されるO(nm log m)前処理、O(m log m)クエリごとに予想される。
単語のm log m文字の単純な並べ替えを行うことを前提としています。
クエリごとにかかる時間は、リスト内の単語数の影響を受けないと予想されます (つまり、ハッシュ マップは予想されるO(1)ルックアップ時間を示します)。