w**t
发帖数: 23 | 1 A long string text, given some characters, find the shortest
substring covering all given characters.
请问大家有没有想法，谢谢 |
f*******4
发帖数: 1401 | 2 quick thoughts：
两个指针p,q，先前进q直到cover了所有characters，记录当前长度
然后单步前进q，每次都尽量前进p使得pq间仍旧cover了所有characters，
maintain最短长度
需要用一个map维护出现的字符
复杂度O(n)因为相当于scan了2次 |
w**t
发帖数: 23 | 3 谢谢，思路挺好
【在 f*******4 的大作中提到】
: quick thoughts：
: 两个指针p,q，先前进q直到cover了所有characters，记录当前长度
: 然后单步前进q，每次都尽量前进p使得pq间仍旧cover了所有characters，
: maintain最短长度
: 需要用一个map维护出现的字符
: 复杂度O(n)因为相当于scan了2次
|
L***Q
发帖数: 508 | 4 假设str[0..n-1]表示整个字符串。基本思路是从str[0]开始，以每个位置作为substring的起点，从该位置往后直到substring能cover所有字符。那么最多就有n个起点。问题是，如何每次只用O(1)来确定substring长度。
我想可以用一个辅助数组记录每种字符出现在字符串中的位置。例如字符a出现在str[0]和str[20]两个地方。假设当前已经确定以str[0]为起点的substring长度。接下来应该确定以str[1]为起点的substring长度。该substring丢弃了str[0]，所以必须要至少在str[20]结束，否则字符a没被cover。这就是基本思路。
我用一个例子解释整个算法。假设字符串包括0到9的数字，整个串如下
0247324596818329654001378
第一步扫描字符串，记录下每种字符位置，如下
0：0，19，20
1：11，21
2：1，5，14
3：4，13，22
4：2，6，18
5：7，17
6：9，16
7：3，23
8：10，12，24
9：8，15
第二步，以str[0]为起点，substring的终点在str[11].
接下来，以str[1]为起点，因为丢弃了str[0]，即字符0，那么从辅助数组可以找到下一个字符0出现在str[19]，因此substring结束于str[19]。
这样每次substring起点往后一个字符，用O(1)时间可以确定结束位置。
【在 w**t 的大作中提到】
: A long string text, given some characters, find the shortest
: substring covering all given characters.
: 请问大家有没有想法，谢谢
|
z**c
发帖数: 625 | 5 请问如何判断“pq间仍旧cover了所有characters”？是用你说的map吗？如果是的话，
key和value是什么呢？
【在 f*******4 的大作中提到】
: quick thoughts：
: 两个指针p,q，先前进q直到cover了所有characters，记录当前长度
: 然后单步前进q，每次都尽量前进p使得pq间仍旧cover了所有characters，
: maintain最短长度
: 需要用一个map维护出现的字符
: 复杂度O(n)因为相当于scan了2次
|
g*********e
发帖数: 14401 | 6
maybe by counting the number of appearance for every char in the current p
to q?
when appearance is 0, you can't move p one step further.
【在 z**c 的大作中提到】
: 请问如何判断“pq间仍旧cover了所有characters”？是用你说的map吗？如果是的话，
: key和value是什么呢？
|
z**c
发帖数: 625 | 7 forever84说的是用map来存这个pq之间的信息,我只是不明白这个检查是O(1)的吗?
难道不需要检查每个字符都在这个map吗?那么如果那个小字符串长度是K,整个复杂度不
就是O(N*K)了?
还是我哪里理解错了?
【在 g*********e 的大作中提到】
:
: maybe by counting the number of appearance for every char in the current p
: to q?
: when appearance is 0, you can't move p one step further.
|
j******a
发帖数: 55 | 8
substring的起
点，从该位置往后直到substring能cover所有字符。那么最多就有n个起点。问题是，
如何每次只用
O(1)来确定substring长度。
[0]和str[20]
两个地方。假设当前已经确定以str[0]为起点的substring长度。接下来应该确定以str
[1]为起点的
substring长度。该substring丢弃了str[0]，所以必须要至少在str[20]结束，否则字
符a没被
cover。这就是基本思路。
这个空间复杂度有点高，不如ls的想法，只需要动态更新一个histogram,时间复杂度都
是2n
【在 L***Q 的大作中提到】
: 假设str[0..n-1]表示整个字符串。基本思路是从str[0]开始，以每个位置作为substring的起点，从该位置往后直到substring能cover所有字符。那么最多就有n个起点。问题是，如何每次只用O(1)来确定substring长度。
: 我想可以用一个辅助数组记录每种字符出现在字符串中的位置。例如字符a出现在str[0]和str[20]两个地方。假设当前已经确定以str[0]为起点的substring长度。接下来应该确定以str[1]为起点的substring长度。该substring丢弃了str[0]，所以必须要至少在str[20]结束，否则字符a没被cover。这就是基本思路。
: 我用一个例子解释整个算法。假设字符串包括0到9的数字，整个串如下
: 0247324596818329654001378
: 第一步扫描字符串，记录下每种字符位置，如下
: 0：0，19，20
: 1：11，21
: 2：1，5，14
: 3：4，13，22
: 4：2，6，18
|
i**********e
发帖数: 1145 | |
