2

どのアルゴリズムを適用すればよいか知りたかったのです。

彼らは与えられた文と単語のリストです。単語のリスト内のすべての単語を含む最初の最短のサブ セグメントを見つける必要があります。

例えば：

文 - これは私が今までに解決した中で最高の問題です

単語リスト -

は

一番

これ

答えは次のとおりです。

これが一番

そのようなサブ セグメントが多数ある場合は、最小数の単語を含み、文の最初に表示されるセグメントを出力する必要があります。

4

2 に答える 2

5

上記の問題を解決するための私のアプローチは次のとおりです。

1。頭と尾の両方が0を指す2つのポインターを取ります

次に、ヘッドポインターが指す単語が有効なキーワードになるまで、ヘッドポインターを移動します。今それを頭としてマークします。

2。次に、文に指定されたすべてのキーワードが少なくとも1回含まれるまで、テールポインタを移動します。今それをしっぽとしてマークします。

そして、これはすべての有効なキーワードを持つ最初の有効なサブセグメントであり、その長さを計算します

3。次に、先頭の単語の頻度を確認します。1より大きい場合は、有効なキーワードであり、単語の頻度が1である文の単語に、先頭のポインタを移動します。

4。次に、すべてのキーワードが存在するかどうかを確認します。存在する場合は、その長さを計算し、最小サブセグメントとして保存します。

5。すべての有効なキーワードが含まれていない場合は、すべてのキーワードが見つかるまでテールポインターを移動し、（tail-head + 1）のように長さを計算します。最小値よりも大きい場合は無視してください。

6。次に、指定された文の最後のキーワードまでこのプロセスを続けます

上記のアプローチの複雑さはo（n）です。

たとえば、このセンチメントを見てみましょう

Hi this is a funny world this is a good experience with this world

そして私は3つのキーワードを見つける必要があります

this
is
world

最初に2つのハッシュテーブル、つまり必須を検討します。取得したすべての必須キーワードを必須テーブルに格納します。

頭と尻尾を0として、頭を動かさないのでhiが有効なキーワードであることを確認します。

次のキーワード、つまりthisを確認します。これは有効なキーワードなので、1を数えて、この単語の位置をheadとして保存します。headは1になります。

次のキーワードが「is」になるようにテールポインタを移動します。これは有効なキーワードであるため、インクリメントカウントも同様にa、funnyキーワードをチェックします。これは、有効なキーワードではないため、テールをワールドに移動します。

これで、worldは有効なものになり、countは3、tailは4になります。count==必要なキーワードがない場合（この場合は3）、セグメントにすべての有効なキーワードが含まれていることを意味します。

今では長さは（4-1 + 1）=4です

ここで、ヘッドの単語の頻度を確認します。これは1つであるため、このヘッドポインターを移動すると、有効なセグメントが取得されません。

テールポインタを次の単語に移動します。これにより、この頻度が1から2に更新され、カウンタが4になります。

これで、ヘッドポインターを移動できるようになりました。キーワードに移動すると、カウンターが3に更新されます。これは、このキーワードからヘッドポインターをシフトしたため、現時点ではセグメントにこれが含まれていないためです。

ここでもカウントは3なので、長さを計算します。これも4です。

したがって、headキーワードのfreqを確認してください。1であるため、テールポインタを次のキーワードに移動します。キーワードfreqは1より大きいため、freqで有効なキーワードを取得するまでheadポインタを移動します。取得したキーワードはworldであり、headpositionはです。 5、テール位置は7、カウンターは3なので、長さを7-5 + 1として計算します。これは3です。したがって、これはこれまでに見つかった最小の長さです。

頭のキーワードfreqが1以上になるまで尻尾を動かします。ついに尻尾が13になります。

頭を5から6に移動して長さを計算すると、13-6 + 1になります。これは8なので、無視してください。

さらに、テールを移動できないため、最終結果としてmin_headからmin_tailに単語を出力します。

私たちの場合、答えは

世界これは

于 2012-07-08T17:50:27.847 に答える
1

次の簡単なアプローチを検討してください -

文中の各単語の辞書マッピング (列挙) を作成します。お気に入り -

これ[1]は[2][3]最高[4]問題[5]私[6]これまで[7]これまでに[8]解決済み[9]

すべてが文中の別個の単語であると仮定します。

ここで、一度に 1 つの単語を取得し、その単語の最大値と最小値の記録をキーとして保持します。この場合、それぞれ 4 と 1 になります。制限内の文字列を返します。

于 2012-06-30T07:38:54.340 に答える