0

ハッシュテーブルとトライを使用して、文字列 (単語) のすべてのアナグラム (つまり、Team が tame という単語を生成する) を検索する手順について、しばらくの間インターネットを検索してきました。SOでここで見つけたのは、2つの単語がアナグラムであることを確認することだけです. さらに一歩進んで、英語でアルゴリズムを見つけて、Javaでプログラミングできるようにしたいと思います。

例えば、

  • すべての文字をループします。
  • 一意の文字ごとにハッシュテーブルに挿入します。
  • など。

完全なプログラムは必要ありません。はい、面接の練習をしています。この質問が出てきたら、私はそれを知り、暗記するだけでなく説明する方法も知っています.

4

3 に答える 3

4

「プログラミングパール」の本で引用された人による最も簡潔な答えは（言い換え）です：

「このように並べ替えます (水平に左から右に手を振る)、次にそのように並べ替えます (垂直に上から下に手を振る)」

つまり、1 列のテーブル (単語) から開始して、2 列のテーブル (sorted_word, word) を作成し、最初の列で並べ替えます。

単語のアナグラムを見つけるには、最初にソートされた単語を計算し、テーブルの最初の列で最初に出現する単語をバイナリ検索し、最初の列が同じである間に 2 番目の列の値を読み取ります。

入力(ソートする必要はありません):

mate
tame
mote
team
tome

「このように」（水平に）ソート：

aemt, mate
aemt, tame
emot, mote
aemt, team
emot, tome

「そのように」（垂直に）ソート：

aemt, mate
aemt, tame
aemt, team
emot, mote
emot, tome

検索 "チーム" -> "aemt"

aemt, mate
aemt, tame
aemt, team

ハッシュテーブル/試行に関しては、ルックアップを少し高速化したい場合にのみ使用されます。ハッシュ テーブルを使用すると、最初の列のハッシュに基づいて、2 列の垂直方向に並べ替えられたテーブルを k パーティションに分割できます。これにより、バイナリ検索を 1 つのパーティション内でのみ実行する必要があるため、一定の速度向上が得られます。試行は、文字列の比較が多すぎるのを避けるのに役立つ最適化の別の方法です。トライの各端末のテーブルの適切なセクションの最初の行のインデックスをぶら下げます。

于 2013-10-25T23:19:53.580 に答える
0
  • Stringにchar[]
  • 並べ替えchar[]
  • Stringソート済みから生成char[]
  • ～の鍵として使うHashMap<String, List<String>>
  • 関連する値のリストに現在の元の文字列を挿入します

たとえば

car, acr, rca, abcそれは持っているだろう

acr: car, acr, rca
abc: abc
于 2013-10-25T22:40:40.193 に答える