字符串x中包含字符串y的所有字符的最小窗口宽度 [英] Minimum window width in string x that contains all characters of string y
问题描述
在字符串 x 中查找最小窗口宽度，该宽度包含另一个字符串 y 的所有字符。例如：
Find minimum window width in string x that contains all characters of another string y. For example:
String x = "coobdafceeaxab"
String y = "abc"
答案应该为5，因为 x 中包含所有内容的最短子字符串 y 的三个字母是 bdafc。
The answer should be 5, because the shortest substring in x that contains all three letters of y is "bdafc".
我可以想到一个天真的解决方案，其复杂度 O（n ^ 2 * log（m）），其中 n = len（x）和 m = len（y）。谁能提出更好的解决方案？谢谢。
I can think of a naive solution with complexity O(n^2 * log(m)), where n = len(x) and m = len(y). Can anyone suggest a better solution? Thanks.
更新：现在考虑一下，如果我将集合更改为 tr1 :: unordered_map ，那么我可以将复杂度降低到 O（n ^ 2），因为插入和删除都应为 O（1） 。
Update: now think of it, if I change my set to tr1::unordered_map, then I can cut the complexity down to O(n^2), because insertion and deletion should both be O(1).
推荐答案
时间：O（n）（一次通过）
空间：O（k）
这就是我的处理方式：
为所有字符串Y中的字符。（我假设所有字符Y都不同）。
This is how I would do it:
Create a hash table for all the characters from string Y. (I assume all characters are different in Y).
第一遍：
从字符串X的第一个字符开始。
更新哈希表，例如：对于密钥' a'输入位置（例如1）。
继续这样做，直到从Y获得所有字符为止（直到哈希表中的所有键都具有值为止）。
如果得到一些字符再次，更新其新值并清除较旧的值。
First pass:
Start from first character of string X.
update hash table, for exa: for key 'a' enter location (say 1).
Keep on doing it until you get all characters from Y (until all key in hash table has value).
If you get some character again, update its newer value and erase older one.
第一次通过后，从哈希表中取最小值，然后取最大值。
Once you have first pass, take smallest value from hash table and biggest value.
Thats the minimum window observed so far.
现在，转到字符串X中的下一个字符，更新哈希表，看看是否得到较小的窗口。
Now, go to next character in string X, update hash table and see if you get smaller window.
编辑：
在这里举个例子：
字符串x = coobdafceeaxab
字符串y = abc
Lets take an example here:
String x = "coobdafceeaxab"
String y = "abc"
首先根据Y的字符初始化哈希表。
h [a] = -1
h [b] = -1
h [c] = -1
First initialize a hash table from characters of Y.
h[a] = -1
h[b] = -1
h[c] = -1
现在，从X的第一个字符开始。
第一个字符是c，h [c] = 0
Secon d字符（o）不是哈希的一部分，请跳过它。
..
第四个字符（b），h [b] = 3
。 。
第六个字符（a），输入哈希表h [a] =5。
现在，哈希表中的所有键都具有一定的值。
最小value是c的0（最大值），a的最大值是5（最大值），到目前为止，最小窗口是6（0到5）。
完成第一遍。
Now, Start from first character of X.
First character is c, h[c] = 0
Second character (o) is not part of hash, skip it.
..
Fourth character (b), h[b] = 3
..
Sixth character(a), enter hash table h[a] = 5.
Now, all keys from hash table has some value.
Smallest value is 0 (of c) and highest value is 5 (of a), minimum window so far is 6 (0 to 5).
First pass is done.
取下一个字符。 f不是哈希表的一部分，请跳过它。
下一个字符（c），更新哈希表h [c] =7。
查找新窗口，最小值为3（ b）的最大值是c的7）。
新窗口是3到7 => 5。
Take next character. f is not part of hash table, skip it.
Next character (c), update hash table h[c] = 7.
Find new window, smallest value is 3 (of b) and highest value is 7 (of c).
New window is 3 to 7 => 5.
继续这样做直到字符串X的最后一个字符。
Keep on doing it till last character of string X.
我希望现在可以清除它。
编辑
I hope its clear now.
Edit
对于从哈希中查找最大值和最小值有一些担忧。
我们可以维护排序后的链接列表并将其与哈希表进行映射。
每当链接列表中的任何元素发生更改时，都应将其重新映射到哈希表。
这两个操作均为O（1）
There are some concerns about finding max and min value from hash.
We can maintain sorted Link-list and map it with hash table.
Whenever any element from Link list changes, it should be re-mapped to hash table.
Both these operation are O(1)
总空间为m + m
编辑
以下是上述问题的小示意图：
对于 coobdafceeaxab和 abc
Here is small visualisation of above problem: For "coobdafceeaxab" and "abc"
step-0：
初始双链表= NULL
初始哈希表= NULL
step-0:
Initial doubly linked-list = NULL
Initial hash-table = NULL
step-1：
Head <-> [c，0] <-> tail
h [c] = [0，'指向c节点的指针在LL']
step-1:
Head<->[c,0]<->tail
h[c] = [0, 'pointer to c node in LL']
步骤2：
Head <-> [c，0] <-> [b，3]< -> tail
h [c] = [0，'指向LL中的c节点的指针']，h [b] = [3，'指向LL中的b节点的指针']，
step-2:
Head<->[c,0]<->[b,3]<->tail
h[c] = [0, 'pointer to c node in LL'], h[b] = [3, 'pointer to b node in LL'],
第3步：
头<-> [c，0] <-> [b，3] <-> [a，5] < -> tail
h [c] = [0，'指向LL中的c节点的指针']，h [b] = [3，'指向LL中的b节点的指针']，h [a] = [5，'指向LL中的节点的指针']
最小窗口=>尾巴与头部的差=>（5-0）+1 =>长度：6
Step-3:
Head<->[c,0]<->[b,3]<->[a,5]<->tail
h[c] = [0, 'pointer to c node in LL'], h[b] = [3, 'pointer to b node in LL'], h[a] = [5, 'pointer to a node in LL']
Minimum Window => difference from tail and head => (5-0)+1 => Length: 6
步骤4：
在此处将C的条目更新为索引7。 （从链接列表中删除 c节点，并在尾部追加）
Head <-> [b，3] <-> [a，5] <-> [c，7] <-> tail
h [c] = [7，'指向LL中c节点的新指针']，h [b] = [3，'指向LL中b节点的指针']，h [ a] = [5，指向LL中节点的指针]，
最小窗口=>尾与头的差=>（7-3）+1 =>长度：5
Step-4:
Update entry of C to index 7 here. (Remove 'c' node from linked-list and append at the tail)
Head<->[b,3]<->[a,5]<->[c,7]<->tail
h[c] = [7, 'new pointer to c node in LL'], h[b] = [3, 'pointer to b node in LL'], h[a] = [5, 'pointer to a node in LL'],
Minimum Window => difference from tail and head => (7-3)+1 => Length: 5
依此类推。
请注意，上面的链接列表更新和哈希表更新均为O（1）。 br>
如果我错了，请纠正我。.
Note that above Linked-list update and hash table update are both O(1).
Please correct me if I am wrong..
摘要：
时间复杂度：O（n）一遍
空间复杂度：O（k）其中k是字符串Y的长度
TIme complexity: O(n) with one pass
Space Complexity: O(k) where k is length of string Y
这篇关于字符串x中包含字符串y的所有字符的最小窗口宽度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
