長さ 100 文字の文字列が 1000 個あるとします。タスクは、すべての文字列の最小部分文字列の長さを計算することです。これは、1000 個の文字列によって生成されたすべての部分文字列の中で一意です。
私のアプローチ
文字列ごとに長さ 1 ～ 100 のすべてのサブ文字列を生成してマップに格納し、重複するサブ文字列が見つかった場合はカウントを増やし続けます。
長さ 1 から始まる文字列ごとにすべての部分文字列を再生成し、長さ L の部分文字列のいずれかのカウントが 1 の場合、L を出力します。
観察
- このソリューションは、C++ で TLE を取得し、Java で渡します。同じことに対する私の理解は、 stl::map 操作は log(N) 時間で行われますが、HashMap 操作は O(1) で行われます。
問題
- 私は解決策を考えており、独自のハッシュを実装しています。私が直面している問題は、1)ハッシュ配列のサイズに適切な値を選択することです2)指定された文字列からハッシュを生成して、衝突を回避できるようにするにはどうすればよいですか?多くの。
上記の問題に対する他の最適なアプローチは評価できます。