0
一定の時間内の単語の平等を決定しますすべての単語の長さがnである場合）、O（n）時間内の単語に対して何らかの操作を実行し、2単語が比較されるたびに、O（1）時間内に回答が一致するかどうかを返します。考えるとk個の言葉は、私はこの質問に遭遇した
それは興味深い質問ですが、私はそれに対処するための任意の方向を見つけることができませんでした...
A
答えて
0
は、単語のすべてのトライを構築し、各単語のために、アレイ内の最後の文字のインデックスを格納します。これはO(n)操作です。
与えられた2つの単語は、それらの最後の文字のインデックスが同じ場合に限り同じです。
すべての単語を配列に格納し、一定の時間内にジョブを終了させたい場合は、配列のインデックスで単語を指定する必要があります。それがうまくいくならば、あなたはすべての単語のハッシュ値を必要とするだけです。 –
ハッシュテーブルは私にO（1）の平均時間複雑度を与えますが、最悪のケースではO（n） いいえenogh ... –