string - 找到最短的子段

Question

我想知道我应该应用哪个算法。

他们是给定的句子和单词列表。我们必须找到包含单词列表中所有单词的第一个最短子段。

例如:

Sentence - this is the best problem i have ever solved

单词列表-

is

best

this

答案应该是:

this is the best

如果有很多这样的子片段，那么我们必须打印出包含最少单词并出现在句子中第一个的那个。

Answer 1

这是我解决上述问题的方法。

1。取2个指针head和tail都指向0

现在移动头指针，直到头指针指向的词是有效关键字；现在将其标记为头部。

2。现在移动尾指针，直到句子至少包含一次所有给定的关键字；现在将其标记为尾部。

这是具有所有有效关键字的第一个有效子段并计算它的长度

3。现在检查 head 的词频 - 如果它大于 1，现在将 head 指针移动到句子中的一个词，它是一个有效的关键字，并且它包含的词频为 1。

4。现在检查是否所有关键字都存在 - 如果是，计算它的长度并将其存储为最小子段。

5。如果它不包含所有有效关键字，现在移动尾指针，直到找到所有关键字并计算其长度，如 (tail-head+1)；如果它大于 min one 则忽略它。

6。现在继续这个过程，直到给定句子的最后一个关键词

上述方法的复杂度为o(n)。

例如让我们以这句话为例

嗨，这是一个有趣的世界，这是一个很好的世界体验

我需要找到 3 个关键字

this
is
world

首先考虑需要2个哈希表，得到 现在将所有必需的关键字存储在必需的表中。

现在将 head 和 tail 设为 0 现在检查 hi 是一个有效的关键字，因为它不会移动 head

现在检查下一个关键字，即 this，现在这是一个有效的关键字，所以计算 1 并将这个词的位置存储为 head。所以现在 head 是 1

现在移动尾指针所以下一个关键字是"is"，它是一个有效的因此增加计数 现在同样检查一个有趣的关键字，因为它们不是有效的关键字，因此将 tail 移到 world

现在 world 是一个有效的并且 count 是 3 并且 tail 是 4 每当 count == no of required keywords(在我们的例子中它是 3)这意味着我们的段包含所有有效的关键字

现在它的长度是 (4-1+1)=4

现在检查开头单词的频率它是一个因此如果我们移动这个开头指针那么我们将不会得到一个有效的段

所以现在将尾指针移动到下一个单词 this 现在将 this 的频率从 1 更新为 2，计数器变为 4

所以现在我们可以移动我们的头指针现在移动到一个关键字现在更新计数器为 3 因为我们的段此时不会包含它因为我们已经从这个关键字转移了头指针

现在再次计数为 3，因此再次计算它的长度为 4

所以检查 head 关键字的 freq 是否为 1 因此将 tail 指针移动到下一个关键字现在是关键字 freq 大于 1 因此现在移动 head 指针直到我们得到一个 freq 为 1 的有效关键字现在获得关键字是 world，头部位置是 5，尾部位置是 7 计数器为 3，所以计算长度为 7-5+1，即 3，因此这是我们迄今为止发现的最小长度

现在移动尾部直到头部的关键字频率大于 1 现在我们的尾部变成 13

现在将头从 5 移动到 6 计算它的长度，它变成 13-6+1 即 8 所以忽略它

现在我们不能移动我们的尾部因此打印从 min_head 到 min_tail 的单词作为最终结果

在我们的例子中答案是

这是世界