string - 找到最短的子段

Question

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

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

例如：

句子 - 这是我解决过的最好的问题

单词列表 -

是

最好的

这个

答案应该是：

这是最好的

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

Answer 1

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

1 . 取2个指针头尾都指向0

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

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

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

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个哈希表，现在将所有需要的关键字存储在所需的表中。

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

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

现在移动尾指针，所以下一个关键字是“是”，它是一个有效的，因此增加计数现在类似地检查一个有趣的关键字，因为它们不是有效的，因此将尾移动到世界

现在 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 因此将尾指针移动到下一个关键字现在是关键字 freq 大于 1 因此现在移动 head 指针，直到我们得到一个有效关键字，其 freq 为 1 现在获得的关键字是 world 和 head 位置是5，尾部位置为 7，计数器为 3，因此计算长度为 7-5+1，即 3，因此这是我们迄今为止发现的最小长度

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

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

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

在我们的例子中，答案是

这是世界

Answer 2

考虑以下简单的方法 -

为句子中的每个单词做一个字典映射（枚举）。喜欢 -

this[1] is[2] the[3] best[4] problem[5] i[6] have[7] ever[8] 已解决[9]

假设所有都是句子中不同的单词。

现在，一次取一个单词，并记录该单词的最大值和最小值作为键。在这种情况下，它将分别是 4 和 1。返回限制范围内的字符串。