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

Question

我最近遇到了一个关于字符串的有趣问题.假设您有以下内容:

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

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

Answer 1

要查看更多详细信息,包括工作代码,请查看我的博客文章:

http://www.leetcode.com/2010/11/finding-minimum-window-in-s-which.html

为了帮助说明这种方法,我使用了一个例子:string1 = "acbbaca"和string2 = "aba".在这里,我们还使用术语"窗口",这意味着来自string1的连续字符块(可以与术语子字符串互换).

i)string1 ="acbbaca"和string2 ="aba".

ii)找到第一个最小窗口.请注意,我们不能将开始指针提升为hasFound ['a'] == needToFind ['a'] == 2.前进意味着打破约束.

iii)找到第二个窗口.开始指针仍然指向第一个元素'a'.hasFound ['a'](3)大于needToFind ['a'](2).我们将hasFound ['a']递减1并向前推进指向右边的指针.

iv)我们跳过'c',因为它在string2中找不到.开始指针现在指向'b'.hasFound ['b'](2)大于needToFind ['b'](1).我们将hasFound ['b']减1,然后将指针向右推进.

v)开始指针现在指向下一个'b'.hasFound ['b'](1)等于needToFind ['b'](1).我们立即停止,这是我们新发现的最小窗口.

这个想法主要是基于两个指针(窗口的开始和结束位置)和两个表(needToFind和hasFound)的帮助,同时遍历string1.needToFind存储string2中字符的总数,hasFound存储到目前为止遇到的字符总数.我们还使用count变量来存储到目前为止遇到的string2中的总字符数(不计算hasFound [x]超过needToFind [x]的字符).当count等于string2的长度时,我们知道找到了一个有效的窗口.

每次我们前进结束指针(指向元素x)时,我们将hasFound [x]递增1.如果hasFound [x]小于或等于needToFind [x],我们也会将count递增1.为什么？当满足约束时(即,count等于string2的大小),我们立即将开始指针尽可能地向前推进,同时保持约束.

我们如何检查它是否维持约束？假设begin指向元素x,我们检查hasFound [x]是否大于needToFind [x].如果是,我们可以将hasFound [x]减1,并在不破坏约束的情况下推进begin指针.另一方面,如果不是,我们会立即停止,因为前进开始指针会破坏窗口约束.

最后,我们检查最小窗口长度是否小于当前最小值.如果找到新的最小值,请更新当前最小值.

本质上,算法找到满足约束的第一个窗口,然后继续保持约束.

Answer 2

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

它的工作原理如下:

• 制作第二个字符串字符的直方图(键操作是hist2[ s2[i] ]++).
• 制作第一个字符串字符的累积直方图,直到该直方图包含第二个字符串的直方图所包含的每个字符(我称之为"直方图条件").
• 然后在第一个字符串上向前移动,从直方图中减去,直到它无法满足直方图条件.将第一个字符串的位(在最后一次移动之前)标记为暂定子字符串.
• 再次向前移动子串的前部,直到再次满足直方图条件.向前移动直到它再次失败.如果这是比第一个更短的子串,则将其标记为暂定子串.
• 重复,直到你通过整个第一个字符串.
• 标记的子字符串是您的答案.

请注意,通过更改您在直方图条件上使用的检查,您可以选择与第二个字符串具有相同的字符集,或者至少选择每种类型的字符数.(它只是之间的差异a[i]>0 && b[i]>0和a[i]>=b[i].)

如果您在尝试满足条件时跟踪哪个条件不满足,并且只检查在您尝试破坏它时减少的东西,则可以加快直方图检查.(在初始构建时,计算您满意的项目数,并在每次添加将条件从false变为true的新字符时增加该计数.)

Answer 3

这是一个O(n)解决方案.基本思路很简单:对于每个起始索引,找到最小结束索引,使子串包含所有必需的字母.诀窍是最小结束索引在函数过程中增加,因此在一点数据结构支持下,我们最多考虑每个字符两次.

在Python中:

from collections import defaultdict

def smallest(s1, s2):
    assert s2 != ''
    d = defaultdict(int)
    nneg = [0]  # number of negative entries in d
    def incr(c):
        d[c] += 1
        if d[c] == 0:
            nneg[0] -= 1
    def decr(c):
        if d[c] == 0:
            nneg[0] += 1
        d[c] -= 1
    for c in s2:
        decr(c)
    minlen = len(s1) + 1
    j = 0
    for i in xrange(len(s1)):
        while nneg[0] > 0:
            if j >= len(s1):
                return minlen
            incr(s1[j])
            j += 1
        minlen = min(minlen, j - i)
        decr(s1[i])
    return minlen