如何找到包含给定字符串中所有字符的最小子字符串？

  • Z时代
  • 2024-01-10
  • 分类：问答

我最近遇到了一个关于字符串的有趣问题。假设您得到以下信息： 

Input string1: "this is a test string"
Input string2: "tist"
Output string: "t stri"

因此，如上所述，我如何找到包含字符串2中所有字符的string1的最小子字符串？

回答：

您可以在O(N+M)时间和O(1)空间上进行直方图扫描，其中N是第一个字符串中M的字符数，而第二个字符串中的字符数。

它是这样的：

  • 制作第二个字符串的字符的直方图（键操作为hist2[ s2[i] ]++）。

  • 制作第一个字符串的字符的累积直方图，直到该直方图包含第二个字符串的直方图包含的每个字符（我将其称为“直方图条件”）。

  • 然后向前移动第一个字符串，从直方图中减去，直到它不满足直方图的条件。将第一个字符串的那一部分（最后一步之前）标记为您的暂定子字符串。

  • 再次向前移动子字符串的前端，直到再次满足直方图条件为止。将末端向前移动，直到再次失败。如果这是比第一个短的子字符串，请将其标记为您的暂定子字符串。

  • 重复直到您遍历了整个第一个字符串。

  • 标记的子字符串是您的答案。

请注意，通过改变您在直方图条件上使用的检查，您可以选择具有 与 第二个字符串 相同的字符集 ，或者 每种类型的字符数最少

。（它只是之间的差异a[i]>0 && b[i]>0和a[i]>=b[i]。）

如果您跟踪想要满足的条件不满足的条件，则可以加快直方图的检查速度，并在尝试破坏条件时仅检查您递减的值。（在初始构建时，您要计算满足的项目数，并在每次添加将条件从false变为true的新字符时递增该计数。）

以上是 如何找到包含给定字符串中所有字符的最小子字符串？ 的全部内容， 来源链接： utcz.com/qa/414630.html

回到顶部