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

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 的连续字符 block (可以与术语子字符串互换)。

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

ii) The first minimum window is found. Notice that we cannot advance begin pointer as hasFound['a'] == needToFind['a'] == 2. Advancing would mean breaking the constraint.

iii) The second window is found. begin pointer still points to the first element 'a'. hasFound['a'] (3) is greater than needToFind['a'] (2). We decrement hasFound['a'] by one and advance begin pointer to the right.

iv) We skip 'c' since it is not found in string2. Begin pointer now points to 'b'. hasFound['b'] (2) is greater than needToFind['b'] (1). We decrement hasFound['b'] by one and advance begin pointer to the right.

v) Begin pointer now points to the next 'b'. hasFound['b'] (1) is equal to needToFind['b'] (1). We stop immediately and this is our newly found minimum window.

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

每次我们推进结束指针(指向一个元素 x)，我们将 hasFound[x] 递增 1。如果 hasFound[x] 小于或等于 needToFind[x]，我们还将计数加一。为什么？当满足约束时(即计数等于 string2 的大小)，我们立即将开始指针尽可能向右推进，同时保持约束。

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

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

本质上，算法会找到第一个满足约束的窗口，然后自始至终继续保持约束。