最小窗口宽度字符串x包含所有字符序列Y [英] Minimum window width in string x that contains all characters in string y

问题描述

查找最小窗口宽度字符串x，它包含的所有字符的字符串年。

Find minimum window width in string x that contains all characters in string y.

例如。

String x = "coobdafceeaxab"
String y = "abc"

答案应该是5，因为最短的子串x中包含所有三个字母y是bdafc。

Answer should be 5 because the shortest substring in x that contains all three letters in y is "bdafc".

我能想到的一个天真的解决方案的复杂性N ^ 2 *日志（M），说N = LEN（x）和M = LEN（Y）。谁能想到一个更好的解决办法？谢谢你。

I can think of a naive solution with complexity n^2 * log(m), say n = len(x) and m = len(y). Can anyone think of a better solution? Thanks.

更新：现在想起来，如果我改变我的设置为TR1 :: unordered_map，然后我就可以削减下来到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 n^2, because insertion and deletion should both be O(1).

推荐答案

时间：O（N）（一号通）
空间：O（K）

time: O(n) (One pass)
space: 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
第一个字符开始 更新哈希表，对于EXA：关键'A'输入位置（比如1）
。 继续做，直到你得到Ÿ的所有字符（直到哈希表中的所有键有值）。
如果再次得到一些字符，更新其新的价值，并删除旧的之一。

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 [α] = -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

现在，从十
第一个字符开始 第一个字符是C，H [C] = 0
第二个字符（O）是不是哈希的一部分，跳过它。
..
第四个字符（二）中，h并[b] = 3
..
第六个字符（a）中，输入哈希表H [α] = 5
现在，从哈希表中的所有键有一定价值。
最小的值是0（的c）和最高值是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）和最高值是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

Total space would be m+m

---

修改

下面是小可视化的上述问题： 对于coobdafceeaxab和ABC

Here is small visualisation of above problem: For "coobdafceeaxab" and "abc"

步骤0：
初次双向链表= NULL
初始哈希表= NULL

step-0:
Initial doubly linked-list = NULL
Initial hash-table = NULL

步骤1：
头＆LT; - > [C，0]＆LT; - >尾
H [C] = [0，指针在LL C节点']

step-1:
Head<->[c,0]<->tail
h[c] = [0, 'pointer to c node in LL']

步骤2：
头＆LT; - > [C，0]＆LT; - > [B，3] LT; - >尾
H [C] = [0，'指针中的LL C节点'〕中，h并[b] = [3，'指针到b LL节点']，

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：
头＆LT; - > [C，0]＆LT; - > [B，3] LT; - > [一，5]＆LT; - >尾
H [C] = [0，'指针中的LL C节点'〕中，h并[b] = [3，'指针在LL b节点'〕中，h [α] = [5,1'指针中的一个节点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节点从链表并追加在尾部）
头＆LT; - > [B，3] LT; - > [一，5]＆LT; - > [C，7]＆LT; - >尾
H [C] = [7，'新指针中的LL C节点'〕中，h并[b] = [3，'指针在LL b节点'〕中，h [α] = [5,1'指向一个节点在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）。
请纠正我，如果我错了。

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屋！