p*****o
发帖数: 1285 | 1 LeetCode上的题目，我怎么想都是O(kn)，k是T里的unique charater的数目。请问大侠
如何做到O(n)。
附题目：
Given a string S and a string T, find the minimum window in S which will
contain all the characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC". |
Z*****Z
发帖数: 723 | 2 假设T的长度是k，如果你先把T扫一遍所有字母放到一个hashtable里，然后再扫S，对S
里面的每一个字母，查询hashtable的时间是常数，这样算下来时O(k+n)的。
当然这只是复杂度分析不是算法。你O（kn）的算法是怎样的？
【在 p*****o 的大作中提到】
: LeetCode上的题目，我怎么想都是O(kn)，k是T里的unique charater的数目。请问大侠
: 如何做到O(n)。
: 附题目：
: Given a string S and a string T, find the minimum window in S which will
: contain all the characters in T in complexity O(n).
: For example,
: S = "ADOBECODEBANC"
: T = "ABC"
: Minimum window is "BANC".
|
p*****o
发帖数: 1285 | 3 k 出现在用来找T中哪个字母最靠前。具体的，如果S里下一个字母是当前T中最靠前的
字母，替换以后需要找到T中下一个最靠前的字母。
对S
【在 Z*****Z 的大作中提到】
: 假设T的长度是k，如果你先把T扫一遍所有字母放到一个hashtable里，然后再扫S，对S
: 里面的每一个字母，查询hashtable的时间是常数，这样算下来时O(k+n)的。
: 当然这只是复杂度分析不是算法。你O（kn）的算法是怎样的？
|
Z*****Z
发帖数: 723 | 4 嗯，看看这样想行不行：
先扫一遍T，把所有字符出现的次数存到一个hashtable（记做ht）里。
然后再弄另外一个hashtable(ht2)用于计数。
接下来用两个指针head和tail同时扫描S，先寻找初始解，再寻找最优解。
（1）在寻找初始解阶段，不停地advance head，每遇到一个S中的T字符就把ht2的相应
count++，直到ht2中每个key的count都比ht中相应key大（至少不小）。
然后不停地advance tail，每遇到一个S中的T字符就把ht2的相应count--，直到ht2中某
一个key的值恰好等于ht中相应key的值。
这就是初始解，记录之。
（2）寻找最优解。这时tail指向的就是T中最靠前的字符，advance head寻找它，同时
更新ht2，逻辑同（1）。找到之后再更新tail，逻辑也同（1）
不知道说清楚了没有。。。
【在 p*****o 的大作中提到】
: k 出现在用来找T中哪个字母最靠前。具体的，如果S里下一个字母是当前T中最靠前的
: 字母，替换以后需要找到T中下一个最靠前的字母。
:
: 对S
|
t**********h
发帖数: 2273 | 5 这个是dp吧，然后backtracking？
中某
【在 Z*****Z 的大作中提到】
: 嗯，看看这样想行不行：
: 先扫一遍T，把所有字符出现的次数存到一个hashtable（记做ht）里。
: 然后再弄另外一个hashtable(ht2)用于计数。
: 接下来用两个指针head和tail同时扫描S，先寻找初始解，再寻找最优解。
: （1）在寻找初始解阶段，不停地advance head，每遇到一个S中的T字符就把ht2的相应
: count++，直到ht2中每个key的count都比ht中相应key大（至少不小）。
: 然后不停地advance tail，每遇到一个S中的T字符就把ht2的相应count--，直到ht2中某
: 一个key的值恰好等于ht中相应key的值。
: 这就是初始解，记录之。
: （2）寻找最优解。这时tail指向的就是T中最靠前的字符，advance head寻找它，同时
|
Z*****Z
发帖数: 723 | 6 我描述的这个方法不是DP也没有BT。要是高富帅知道更好或者更正确的做法请share :)
【在 t**********h 的大作中提到】
: 这个是dp吧，然后backtracking？
:
: 中某
|
p*****o
发帖数: 1285 | 7 en,跟我后来想到的差不多。不需要两个hashtable，可以用一个hashtable，节点用
queue，其中放字符出现的位置。
中某
【在 Z*****Z 的大作中提到】
: 嗯，看看这样想行不行：
: 先扫一遍T，把所有字符出现的次数存到一个hashtable（记做ht）里。
: 然后再弄另外一个hashtable(ht2)用于计数。
: 接下来用两个指针head和tail同时扫描S，先寻找初始解，再寻找最优解。
: （1）在寻找初始解阶段，不停地advance head，每遇到一个S中的T字符就把ht2的相应
: count++，直到ht2中每个key的count都比ht中相应key大（至少不小）。
: 然后不停地advance tail，每遇到一个S中的T字符就把ht2的相应count--，直到ht2中某
: 一个key的值恰好等于ht中相应key的值。
: 这就是初始解，记录之。
: （2）寻找最优解。这时tail指向的就是T中最靠前的字符，advance head寻找它，同时
|
Z*****Z
发帖数: 723 | 8 Queue其实可以取代tail指针。
关于一个hashtable，你是说把ht干掉还是ht2干掉？只用一个hashtable的话怎么给S和
T同时计数？
【在 p*****o 的大作中提到】
: en,跟我后来想到的差不多。不需要两个hashtable，可以用一个hashtable，节点用
: queue，其中放字符出现的位置。
:
: 中某
|
t**********h
发帖数: 2273 | 9 刚才没认真看，sorry。确实没dp，也没bt。明天有面试，不看新题了，复习复习旧题
，完了上来看大牛们的结论。。。
【在 Z*****Z 的大作中提到】
: 我描述的这个方法不是DP也没有BT。要是高富帅知道更好或者更正确的做法请share :)
|
Z*****Z
发帖数: 723 | 10 bless
【在 t**********h 的大作中提到】
: 刚才没认真看，sorry。确实没dp，也没bt。明天有面试，不看新题了，复习复习旧题
: ，完了上来看大牛们的结论。。。
|
|
|
r********g
发帖数: 1351 | 11 这个：
直到ht2中每个key的count都比ht中相应key大（至少不小）
是不是要遍历所有的key来保证每个的key都满足？那复杂度就是O(km）吧。。。我记得
leetcode的讨论里面有个巧妙的办法来避免遍历，但是原理稍微复杂一点点
中某
【在 Z*****Z 的大作中提到】
: 嗯，看看这样想行不行：
: 先扫一遍T，把所有字符出现的次数存到一个hashtable（记做ht）里。
: 然后再弄另外一个hashtable(ht2)用于计数。
: 接下来用两个指针head和tail同时扫描S，先寻找初始解，再寻找最优解。
: （1）在寻找初始解阶段，不停地advance head，每遇到一个S中的T字符就把ht2的相应
: count++，直到ht2中每个key的count都比ht中相应key大（至少不小）。
: 然后不停地advance tail，每遇到一个S中的T字符就把ht2的相应count--，直到ht2中某
: 一个key的值恰好等于ht中相应key的值。
: 这就是初始解，记录之。
: （2）寻找最优解。这时tail指向的就是T中最靠前的字符，advance head寻找它，同时
|
p*****o
发帖数: 1285 | 12 我的完整的方法是这样的。用两个辅助数据结构，一个hashtable, 每个节点是个固定
长度的queue，长度是该字符在T中的数量，存放T字符在目前序列中的位置。另一个是
queue, 用来存目前序列中属于T的字符的顺序，以方便寻找下一序列起点。不用queue
直接用尾指针也可以，但会增加一些比较。
【在 Z*****Z 的大作中提到】
: Queue其实可以取代tail指针。
: 关于一个hashtable，你是说把ht干掉还是ht2干掉？只用一个hashtable的话怎么给S和
: T同时计数？
|
Z*****Z
发帖数: 723 | 13 不用，搞个counter，初始化为T的长度。在（1）阶段，每次增加ht2 key值的时候，和
ht key比一下，要是ht2的key值小，就把counter --。
counter就是当前所找到的有效字符。
counter为0的时候，条件自然就满足了。
【在 r********g 的大作中提到】
: 这个：
: 直到ht2中每个key的count都比ht中相应key大（至少不小）
: 是不是要遍历所有的key来保证每个的key都满足？那复杂度就是O(km）吧。。。我记得
: leetcode的讨论里面有个巧妙的办法来避免遍历，但是原理稍微复杂一点点
:
: 中某
|
Z*****Z
发帖数: 723 | 14 那也就是说hashtable里每个节点最多就放那么多元素？不是很明白那个hashtable是怎
么更新的
比如在abbcc 里面找abc，那第二个b只放在queue里？
你要是过了leetcode可以直接贴代码，看起来快些:)
queue
【在 p*****o 的大作中提到】
: 我的完整的方法是这样的。用两个辅助数据结构，一个hashtable, 每个节点是个固定
: 长度的queue，长度是该字符在T中的数量，存放T字符在目前序列中的位置。另一个是
: queue, 用来存目前序列中属于T的字符的顺序，以方便寻找下一序列起点。不用queue
: 直接用尾指针也可以，但会增加一些比较。
|
r********g
发帖数: 1351 | 15 嘿嘿俺说的就是这个trick啦，当时看的时候还是觉得很巧妙的。。特别是counter++的
地方
【在 Z*****Z 的大作中提到】
: 不用，搞个counter，初始化为T的长度。在（1）阶段，每次增加ht2 key值的时候，和
: ht key比一下，要是ht2的key值小，就把counter --。
: counter就是当前所找到的有效字符。
: counter为0的时候，条件自然就满足了。
|
p*****o
发帖数: 1285 | 16 T里的元素都放在hashtable的queue里，后面每多加一个前面就拿走一个。这是我最初O
(kn)的code，后来的都没有存。为了方便用的是STL里的map，比hashtable慢一点。
class Solution {
public:
string minWindow(string S, string T) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
map > tbl;
int ct = 0; // counter to find the first full set
int lowest; // lowest index of current set
for (int i=0; i
if (tbl.find(T[i]) == tbl.end()) tbl[T[i]] = queue();
tbl[T[i]].push(-1);
}
int mlen = S.size(), lo = -1; // min length and start position
map >::iterator p, q; // temp iterators
for (int i=0; i < S.size(); ++i) if ((p = tbl.find(S[i])) != tbl.end
()){
if (p->second.front() == -1) ++ct;
p->second.push(i);
p->second.pop();
if (ct == T.size() && (mlen == S.size() || S[i] == S[lowest])) {
lowest = S.size();
for (q = tbl.begin(); q != tbl.end(); ++q)
if (q->second.front() < lowest) lowest = q->second.front
();
int len = i - lowest + 1;
if (len < mlen || len == S.size()){
lo = lowest;
mlen = len;
}
}
}
if (lo == -1) return "";
else return S.substr(lo, mlen);
}
}
【在 Z*****Z 的大作中提到】
: 那也就是说hashtable里每个节点最多就放那么多元素？不是很明白那个hashtable是怎
: 么更新的
: 比如在abbcc 里面找abc，那第二个b只放在queue里？
: 你要是过了leetcode可以直接贴代码，看起来快些:)
:
: queue
|
Z*****Z
发帖数: 723 | 17 不错，这个O（kn）的code挺好看的。
初O
【在 p*****o 的大作中提到】
: T里的元素都放在hashtable的queue里，后面每多加一个前面就拿走一个。这是我最初O
: (kn)的code，后来的都没有存。为了方便用的是STL里的map，比hashtable慢一点。
: class Solution {
: public:
: string minWindow(string S, string T) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: map > tbl;
: int ct = 0; // counter to find the first full set
: int lowest; // lowest index of current set
|
p*****o
发帖数: 1285 | 18 Thanks. Here is the weird thing: this O(kn) method seems faster than any O(
n) implementation I tried. I have tried to mimic a hash table with an array
of 128 elements since LeetCode's test cases are limited to ASCII characters
. For the large test, the O(kn) method with map takes about 140ms, the fake
hash table method with tail pointer takes about 180ms, and the queue
implementation takes about the same amount time.
My guess is that the factor of "k" part is only run very few times, which
makes it better than the 2n methods. What's your thought?
【在 Z*****Z 的大作中提到】
: 不错，这个O（kn）的code挺好看的。
:
: 初O
|
