D********g
发帖数: 650 | 1 给一个字符串s1,和一个小串s2，求算法能在s1中找到包含s2里所有字符的最小子串。
比如，
s1 = "ADOBECODEBANC"
s2 = "ABC"
最小子串是 "BANC"
要求O(N)的算法。 |
l**o
发帖数: 356 | 2 先找到第一个包含所有字符的子字符串，对于substring 中出现的第一个B中的字符,在
他之后找第一次出现的位置,substring 后移,找出最短的长度
不知道我说清楚了没有...
【在 D********g 的大作中提到】
: 给一个字符串s1,和一个小串s2，求算法能在s1中找到包含s2里所有字符的最小子串。
: 比如，
: s1 = "ADOBECODEBANC"
: s2 = "ABC"
: 最小子串是 "BANC"
: 要求O(N)的算法。
|
y*********e
发帖数: 518 | 3 视 string 为 bag of chars。把 s1 和 s2 分别转换成 bag of chars，然后找 s1 里
面最小的 substring，使得前者 bag 包含后者。O(n + m)，这里 n 和 m 分别是
s1 和 s2 的长度。
要注意一个 corner case：s1 不包含 s2 所有的 char。比如，s1 = "abc", s2 = "d"
/* C# code
*
* returns null if not found
* assumes ASCII
*/
public string FindSmallestSubStringContains(string s1, string s2) {
if (s2.Length == 0) return String.Empty;
if (s1.Length == 0) return null; // not found
char[] bag1 = new char[128];
char[] bag2 = new char[128];
forea
【在 D********g 的大作中提到】
: 给一个字符串s1,和一个小串s2，求算法能在s1中找到包含s2里所有字符的最小子串。
: 比如，
: s1 = "ADOBECODEBANC"
: s2 = "ABC"
: 最小子串是 "BANC"
: 要求O(N)的算法。
|
p********7
发帖数: 549 | 4 刚才的算法有问题，不能达到O（N），下面这个应该没问题
先遍历一次，记录S2每个char的位置
s1 = "ADOBECODEBANCBBCAA"
s2 = "ABC"
按顺序记录就行了不用管ABC
record是一个DOUBLE链表 0，3，5，9，10，12，13，14，15，16，17，18
下次遍历的时候用一个hashtable，记录位置，并且记录链表node的指针
只用遍历record的位置，并且record最小值
a b c
0 3 5
下面遍历链表中的9，发现hashtable有b，于是获得位置是3的b的指针，删除链表当中值为3的node，并且更新table
链表现在是 0，5，9，10，12.......
a b c
0 9 5
因为更新的不是最小值，所以不计算
下面是10，发现table已经有a，于是获得以前a的node指针，删除链表当中之前的a，更新table，计算当前节点值和head节点值的差，是5，于是不更新
a b c
10 9 5 |
w*********n
发帖数: 48 | 5 能稍稍具体说说第二次遍历的算法吗？
找了一下版上没找到，谢谢
【在 p********7 的大作中提到】
: 刚才的算法有问题，不能达到O（N），下面这个应该没问题
: 先遍历一次，记录S2每个char的位置
: s1 = "ADOBECODEBANCBBCAA"
: s2 = "ABC"
: 按顺序记录就行了不用管ABC
: record是一个DOUBLE链表 0，3，5，9，10，12，13，14，15，16，17，18
: 下次遍历的时候用一个hashtable，记录位置，并且记录链表node的指针
: 只用遍历record的位置，并且record最小值
: a b c
: 0 3 5
|
y*********e
发帖数: 518 | 6 我用例子跑了一遍，返回的是正确的结果。
$ mcs FindSmallestSubStringContains.cs
$ mono FindSmallestSubStringContains.exe ADOBECODEBANC ABC
BANC |
t****z
发帖数: 229 | 7 try ABCDA
【在 y*********e 的大作中提到】
: 我用例子跑了一遍，返回的是正确的结果。
: $ mcs FindSmallestSubStringContains.cs
: $ mono FindSmallestSubStringContains.exe ADOBECODEBANC ABC
: BANC
|
p********7
发帖数: 549 | 8 我更新算法了，看上面的帖子
【在 w*********n 的大作中提到】
: 能稍稍具体说说第二次遍历的算法吗？
: 找了一下版上没找到，谢谢
|
h**k
发帖数: 3368 | 9 对，他的算法不能处理这个case。实际上在左右指针都指向同一个s2中出现的字符时，
你不知道移动哪个指针达到最优解。
【在 t****z 的大作中提到】
: try ABCDA
|
D********g
发帖数: 650 | 10 这个算法是不work，不过还是很清晰，能保证找到一个从s2字符的角度来讲最小的
window
而且要gover所有的字符，当输入串比较短的时候复杂度不是linear的了
【在 t****z 的大作中提到】
: try ABCDA
|
|
|
t****z
发帖数: 229 | 11 does it work for "ABDBAC"?
【在 p********7 的大作中提到】
: 刚才的算法有问题，不能达到O（N），下面这个应该没问题
: 先遍历一次，记录S2每个char的位置
: s1 = "ADOBECODEBANCBBCAA"
: s2 = "ABC"
: 按顺序记录就行了不用管ABC
: record是一个DOUBLE链表 0，3，5，9，10，12，13，14，15，16，17，18
: 下次遍历的时候用一个hashtable，记录位置，并且记录链表node的指针
: 只用遍历record的位置，并且record最小值
: a b c
: 0 3 5
|
s*****n
发帖数: 5488 | 12
这一步怎么能够O(n)实现？而不是O(nm)或者O(nlogm)?
【在 p********7 的大作中提到】
: 刚才的算法有问题，不能达到O（N），下面这个应该没问题
: 先遍历一次，记录S2每个char的位置
: s1 = "ADOBECODEBANCBBCAA"
: s2 = "ABC"
: 按顺序记录就行了不用管ABC
: record是一个DOUBLE链表 0，3，5，9，10，12，13，14，15，16，17，18
: 下次遍历的时候用一个hashtable，记录位置，并且记录链表node的指针
: 只用遍历record的位置，并且record最小值
: a b c
: 0 3 5
|
p********7
发帖数: 549 | 13 你说的是哪一步？
我想了下，链表应该是doublelinked的
建立链表肯定是O（N）
顺着链表遍历一次，还是O（N）啊，虽然有删除操作，但是删除不需要遍历，从
hashtable就能直接找到需要删除的节点。删除操作也是O(N)
hashtable记录O（1）
【在 s*****n 的大作中提到】
:
: 这一步怎么能够O(n)实现？而不是O(nm)或者O(nlogm)?
|
h**6
发帖数: 4160 | 14 只用遍历record的位置，并且record最小值
a b c
0 3 5
下面遍历链表中的9，发现hashtable有b，于是获得位置是3的b的指针，删除链表当中值为3的node，并且更新table
链表现在是 0，5，9，10，12.......
a b c
0 9 5
这一步，删除链表中的3，恐怕无法用O(1)实现吧 |
s*****n
发帖数: 5488 | 15 记录S2每个字符的位置。这一步怎么实现的？也就是说你怎么知道是s2中的字符
【在 p********7 的大作中提到】
: 你说的是哪一步？
: 我想了下，链表应该是doublelinked的
: 建立链表肯定是O（N）
: 顺着链表遍历一次，还是O（N）啊，虽然有删除操作，但是删除不需要遍历，从
: hashtable就能直接找到需要删除的节点。删除操作也是O(N)
: hashtable记录O（1）
|
h**6
发帖数: 4160 | 16 我的方法是先找到第一个包含所有字符的子字符串，用两个指针分别指向子串头尾，一
个数组统计各字符出现次数。此后首先考虑移动左指针。
1.左指针移动，每次右移更新子串最短长度。
1)若左指针指向字符不是B串中字符，左指针右移；
2)若左指针指向字符是B串中字符，且在子串中出现次数不止一次，左指针右移并减去
一次出现次数；
3)若左指针指向字符是B串中字符，且只在子串中出现一次，左指针不动，换右指针。
2.右指针移动。
1)若右指针指向字符不是B串中字符，右指针右移；
2)若右指针指向字符是B串中字符，且不是左指针指向的字符，右指针右移并增加一次
出现次数；
3)若右指针指向字符是B串中字符，且是左指针指向的字符，右指针右移并增加一次出
现次数，换左指针。 |
z****n
发帖数: 1379 | 17 这题就是版上讨论过很多遍的找一个文档中包含所有关键字的最小窗口的变体。每个字
符是一个单词，s1相当于文档，s2相当于关键字组合
关于复杂度，我的理解是s2总是远远小于s1(事实上s2最多26），题目中也说了s2是小串
，这样O(N)复杂度其实是要求相对于s1的size N来说是线性的，对s2进行一些排序或者
查找操作都不影响复杂度
所以经典的找最小window算法可以直接拿来用
【在 D********g 的大作中提到】
: 给一个字符串s1,和一个小串s2，求算法能在s1中找到包含s2里所有字符的最小子串。
: 比如，
: s1 = "ADOBECODEBANC"
: s2 = "ABC"
: 最小子串是 "BANC"
: 要求O(N)的算法。
|
r***u
发帖数: 241 | 18 经典算法是什么？
小串
【在 z****n 的大作中提到】
: 这题就是版上讨论过很多遍的找一个文档中包含所有关键字的最小窗口的变体。每个字
: 符是一个单词，s1相当于文档，s2相当于关键字组合
: 关于复杂度，我的理解是s2总是远远小于s1(事实上s2最多26），题目中也说了s2是小串
: ，这样O(N)复杂度其实是要求相对于s1的size N来说是线性的，对s2进行一些排序或者
: 查找操作都不影响复杂度
: 所以经典的找最小window算法可以直接拿来用
|
s*****n
发帖数: 5488 | 19
小串
事实上，O(mn)的算法很好找。但是，第一题目没有说s2远小于s1,第二s2没有说必须
每个字符都不同。AAAAAAAAA也是合理的字串。
【在 z****n 的大作中提到】
: 这题就是版上讨论过很多遍的找一个文档中包含所有关键字的最小窗口的变体。每个字
: 符是一个单词，s1相当于文档，s2相当于关键字组合
: 关于复杂度，我的理解是s2总是远远小于s1(事实上s2最多26），题目中也说了s2是小串
: ，这样O(N)复杂度其实是要求相对于s1的size N来说是线性的，对s2进行一些排序或者
: 查找操作都不影响复杂度
: 所以经典的找最小window算法可以直接拿来用
|
h**k
发帖数: 3368 | 20 如果s2中没有重复字符，让你只扫描一遍s1，有办法么？比如s1是输入的char stream
，由于内存有限，我们只能处理当前读取的char，不能记录所有之前读取的chars。
【在 h**6 的大作中提到】
: 我的方法是先找到第一个包含所有字符的子字符串，用两个指针分别指向子串头尾，一
: 个数组统计各字符出现次数。此后首先考虑移动左指针。
: 1.左指针移动，每次右移更新子串最短长度。
: 1)若左指针指向字符不是B串中字符，左指针右移；
: 2)若左指针指向字符是B串中字符，且在子串中出现次数不止一次，左指针右移并减去
: 一次出现次数；
: 3)若左指针指向字符是B串中字符，且只在子串中出现一次，左指针不动，换右指针。
: 2.右指针移动。
: 1)若右指针指向字符不是B串中字符，右指针右移；
: 2)若右指针指向字符是B串中字符，且不是左指针指向的字符，右指针右移并增加一次
|
|
|
p********7
发帖数: 549 | 21 为什么不能?我在hashtable记录了3的节点指针，这个是个双链表，删除操作是O（1）
，如果是单链表就不行。
中值为3的node，并且更新table
【在 h**6 的大作中提到】
: 只用遍历record的位置，并且record最小值
: a b c
: 0 3 5
: 下面遍历链表中的9，发现hashtable有b，于是获得位置是3的b的指针，删除链表当中值为3的node，并且更新table
: 链表现在是 0，5，9，10，12.......
: a b c
: 0 9 5
: 这一步，删除链表中的3，恐怕无法用O(1)实现吧
|
z****n
发帖数: 1379 | 22 题目说了是小串。。。
重复的话实际中没有意义，当然较真的话可以重复，这题主要依据还是题目中说了s2是
小串，一般这么说了涵义就很明显了。
【在 s*****n 的大作中提到】
:
: 小串
: 事实上，O(mn)的算法很好找。但是，第一题目没有说s2远小于s1,第二s2没有说必须
: 每个字符都不同。AAAAAAAAA也是合理的字串。
|
A*********r
发帖数: 564 | 23 如果你指的是paul198247 算法中第一步，用O(N)建立一个record记录的话，可以这样
做：
扫描一遍S2, 用hashtable mark出现的字符，
然后再扫描S1, 如果当前字符在hashtable中出现过（即在S2中出现），把当前位置加
入到record即可。。
考虑到S2比较小，这个操作只需要O(N).
【在 s*****n 的大作中提到】
: 记录S2每个字符的位置。这一步怎么实现的？也就是说你怎么知道是s2中的字符
|
h**6
发帖数: 4160 | 24 没看见记录了结点指针，这样的话，确实可行。和刚才那题hit cache有异曲同工之妙。
如果稍微改改，也可以只扫描一次的。
【在 p********7 的大作中提到】
: 为什么不能?我在hashtable记录了3的节点指针，这个是个双链表，删除操作是O（1）
: ，如果是单链表就不行。
:
: 中值为3的node，并且更新table
|
z****n
发帖数: 1379 | 25 先遍历s1找到s2中每个字符出现的位置，由于出现位置可能有多个，所以s2中每个字符
对应一个位置数组，例如
a: 0,3, 5, 11, 15
b: 2,6,10
c: 1,7,8
然后看最左边3个构成的窗口(0,2,1)，窗口大小是2，记录下，再移动值最小的数组的那
个指针（0变成3），新窗口(3,2,1),窗口大小还是2，不用更新最小窗口，再移动值最小
的数组的指针（1变成7），以此类推
【在 r***u 的大作中提到】
: 经典算法是什么？
:
: 小串
|
l******e
发帖数: 12192 | 26 计算最小值是O(1)么？
【在 p********7 的大作中提到】
: 为什么不能?我在hashtable记录了3的节点指针，这个是个双链表，删除操作是O（1）
: ，如果是单链表就不行。
:
: 中值为3的node，并且更新table
|
s*****n
发帖数: 5488 | 27 这也是我想的。但是算窗口大小就是O(m)复杂度了。还能在进一步提高吗？
的那
最小
【在 z****n 的大作中提到】
: 先遍历s1找到s2中每个字符出现的位置，由于出现位置可能有多个，所以s2中每个字符
: 对应一个位置数组，例如
: a: 0,3, 5, 11, 15
: b: 2,6,10
: c: 1,7,8
: 然后看最左边3个构成的窗口(0,2,1)，窗口大小是2，记录下，再移动值最小的数组的那
: 个指针（0变成3），新窗口(3,2,1),窗口大小还是2，不用更新最小窗口，再移动值最小
: 的数组的指针（1变成7），以此类推
|
A*********r
发帖数: 564 | 28 其实我不明白为什么要删除那个节点？
记录的record 链表貌似只需要扫描一遍而已，要不停update的是hashtable中的值，还
有记录当前最小字串的变量。。
【在 p********7 的大作中提到】
: 为什么不能?我在hashtable记录了3的节点指针，这个是个双链表，删除操作是O（1）
: ，如果是单链表就不行。
:
: 中值为3的node，并且更新table
|
r***u
发帖数: 241 | 29 哦，那就是paul198247说的方法了。
的那
最小
【在 z****n 的大作中提到】
: 先遍历s1找到s2中每个字符出现的位置，由于出现位置可能有多个，所以s2中每个字符
: 对应一个位置数组，例如
: a: 0,3, 5, 11, 15
: b: 2,6,10
: c: 1,7,8
: 然后看最左边3个构成的窗口(0,2,1)，窗口大小是2，记录下，再移动值最小的数组的那
: 个指针（0变成3），新窗口(3,2,1),窗口大小还是2，不用更新最小窗口，再移动值最小
: 的数组的指针（1变成7），以此类推
|
z****n
发帖数: 1379 | 30 可以是可以，但是我觉得既然题目说了s2是小串的话，O(mN)可以认为是O(N)的，
【在 s*****n 的大作中提到】
: 这也是我想的。但是算窗口大小就是O(m)复杂度了。还能在进一步提高吗？
:
: 的那
: 最小
|
|
|
p********7
发帖数: 549 | 31 因为你删除了没用的，才能最快获得min位置，链表头永远保持着min的位置
【在 A*********r 的大作中提到】
: 其实我不明白为什么要删除那个节点？
: 记录的record 链表貌似只需要扫描一遍而已，要不停update的是hashtable中的值，还
: 有记录当前最小字串的变量。。
|
A*********r
发帖数: 564 | 32 这个跟paul那个算法很像。。
他那个record就是abc三个位置数组的按顺序排列，然后依次扫描，每次都update
hashtable中出现的abc的位置就好了，只需要O(1）的时间，没觉得是O(m*n).
的那
最小
【在 z****n 的大作中提到】
: 先遍历s1找到s2中每个字符出现的位置，由于出现位置可能有多个，所以s2中每个字符
: 对应一个位置数组，例如
: a: 0,3, 5, 11, 15
: b: 2,6,10
: c: 1,7,8
: 然后看最左边3个构成的窗口(0,2,1)，窗口大小是2，记录下，再移动值最小的数组的那
: 个指针（0变成3），新窗口(3,2,1),窗口大小还是2，不用更新最小窗口，再移动值最小
: 的数组的指针（1变成7），以此类推
|
A*********r
发帖数: 564 | 33 链表头要min，是为了计算当前子串的长度？
看你的例子：
s1 = "ADOBECODEBANCBBCAA"
s2 = "ABC"
0，3，5，9，10，12，13，14，15，16，17
刚开始依次遍历到0，3，5， hashtable为
a b c
0 3 5
计算此时的字串长度为5， 保存当前最小字串
遍历到9，10，
hashtable 依次被更新为 0 9 5 --> 10, 9, 5, 最小index变为5， 所以计算此时的
字符串长度为5，不比之前的更小，不用更新最小字串
继续遍历到12, hashtable 变为 10， 9， 12， 更新长度为3
继续遍历到13， hashtable变为 10，13，12，长度一样，不更新
继续遍历到14,15,16,17, hashtable依次变为
10, 14, 12 -> 10, 15, 12 -> 16, 15, 12 -> 17, 15 , 12
长度都没有被更新。。
唯一的问题就是在hashtable中，计算当前字串长的问题，貌似直接算的话需要O(m).
如果在链表头保留了当前hashtable中最小ind
【在 p********7 的大作中提到】
: 因为你删除了没用的，才能最快获得min位置，链表头永远保持着min的位置
|
p********7
发帖数: 549 | 34 是为了算windows的宽，其实不用遍历2次，第一次遍历就可以建立双链表的同时，结合
hashtable就可以更新以及删除链表节点以及算windows的宽了。
【在 A*********r 的大作中提到】
: 链表头要min，是为了计算当前子串的长度？
: 看你的例子：
: s1 = "ADOBECODEBANCBBCAA"
: s2 = "ABC"
: 0，3，5，9，10，12，13，14，15，16，17
: 刚开始依次遍历到0，3，5， hashtable为
: a b c
: 0 3 5
: 计算此时的字串长度为5， 保存当前最小字串
: 遍历到9，10，
|
h**k
发帖数: 3368 | 35 nod。起作用的只是s2中每个元素最后出现的位置。所以我们不需要记录每个元素出现
的所有位置，而只需要记录每个元素最后出现的位置。
当这个记录里最左面的元素位置变化时，我们需要重新寻找最左面的元素，这需要O(M)
。所以总的时间复杂度是O(MN)。
前面han6说的那个移动两个指针的算法复杂度是O(N)，但是需要扫描两次。
这道题我就被问到过，我当时的解法是第一个，面试官没有找出bug。
【在 A*********r 的大作中提到】
: 链表头要min，是为了计算当前子串的长度？
: 看你的例子：
: s1 = "ADOBECODEBANCBBCAA"
: s2 = "ABC"
: 0，3，5，9，10，12，13，14，15，16，17
: 刚开始依次遍历到0，3，5， hashtable为
: a b c
: 0 3 5
: 计算此时的字串长度为5， 保存当前最小字串
: 遍历到9，10，
|
h**6
发帖数: 4160 | 36 其实我电面时也被问过这题的，我当时给出的经典算法是O(Nlogm)，其中 m 是短串的
长度。今天为了找出O(N)算法，才想到利用两个指针。
不过这两种方法都需要扫描两次。 |
g******d
发帖数: 511 | |
A*********r
发帖数: 564 | 38 感觉这个算法如果s2中包含重复字符的话，就不一定work了。。
【在 h**6 的大作中提到】
: 我的方法是先找到第一个包含所有字符的子字符串，用两个指针分别指向子串头尾，一
: 个数组统计各字符出现次数。此后首先考虑移动左指针。
: 1.左指针移动，每次右移更新子串最短长度。
: 1)若左指针指向字符不是B串中字符，左指针右移；
: 2)若左指针指向字符是B串中字符，且在子串中出现次数不止一次，左指针右移并减去
: 一次出现次数；
: 3)若左指针指向字符是B串中字符，且只在子串中出现一次，左指针不动，换右指针。
: 2.右指针移动。
: 1)若右指针指向字符不是B串中字符，右指针右移；
: 2)若右指针指向字符是B串中字符，且不是左指针指向的字符，右指针右移并增加一次
|
z*****6
发帖数: 17 | 39 同问找最小window的经典算法
【在 s*****n 的大作中提到】
: 这也是我想的。但是算窗口大小就是O(m)复杂度了。还能在进一步提高吗？
:
: 的那
: 最小
|
i**********e
发帖数: 1145 | 40 paul 的方法是 O(N)吗？我怎么觉得像 O(MN）？这是因为每次为了计算字串长度，必须寻找 minimum，所以要遍历 M 次。有人可以解释一下吗？
我想到最直接的优化方法就是保持一个 min heap，能 O(1) 索取 minimum，但是代价就是 insert 和 delete 需要 O(lg M)。总复杂度为 O(N lg M)。
还有值得一提的是，以上的例子小串里没有重复的字母。万一小串是 "AABC" 怎么办呢？以上的方法都不能解决这个情况，只有 han6 的方法似乎比较对的，就是利用两个指针。但是解释得有点复杂，建议看 stormrage 的精简解法（在第9楼）。
http://mitbbs.com/article_t/JobHunting/31731763.html
楼上有人说如果 M 相对 N 很小，可以直接忽略，万一面试官不觉得是这么回事那就完蛋啦。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 p********7 的大作中提到】
: 刚才的算法有问题，不能达到O（N），下面这个应该没问题
: 先遍历一次，记录S2每个char的位置
: s1 = "ADOBECODEBANCBBCAA"
: s2 = "ABC"
: 按顺序记录就行了不用管ABC
: record是一个DOUBLE链表 0，3，5，9，10，12，13，14，15，16，17，18
: 下次遍历的时候用一个hashtable，记录位置，并且记录链表node的指针
: 只用遍历record的位置，并且record最小值
: a b c
: 0 3 5
|
|
|
s****e
发帖数: 139 | |
m*****k
发帖数: 731 | 42 给一个字符串s1,和一个小串s2，求算法能在s1中找到包含s2里所有字符的最小子串。
比如，
s1 = "ADOBECODEBANC"
s2 = "ABC"
A: 0,10,
B: 3, 9,
C: 5,12
(0,3,5) length is 5-0
min 0, remove 0, take next one, say 10
(10,3,5) lenth is 10 -3
min 3, remove, take next, 9
(10,9,5) length is 10 - 5
min 5, remove, take next, 12
(10,9,12) lenth is 12 - 9
min 9, remove, no next, done.
shortest is 12 - 9, which is (10,9,12)
【在 D********g 的大作中提到】
: 给一个字符串s1,和一个小串s2，求算法能在s1中找到包含s2里所有字符的最小子串。
: 比如，
: s1 = "ADOBECODEBANC"
: s2 = "ABC"
: 最小子串是 "BANC"
: 要求O(N)的算法。
|
n********y
发帖数: 66 | 43 0
0 3
0 3 5 => minspan = 5-0+1
0 9 5 => newmin = 9-0+1, discard
10 9 5 => newmin = 10-5+1 discard
10 9 12 => newmin = 12-9+1, update minspan
【在 m*****k 的大作中提到】
: 给一个字符串s1,和一个小串s2，求算法能在s1中找到包含s2里所有字符的最小子串。
: 比如，
: s1 = "ADOBECODEBANC"
: s2 = "ABC"
: A: 0,10,
: B: 3, 9,
: C: 5,12
: (0,3,5) length is 5-0
: min 0, remove 0, take next one, say 10
: (10,3,5) lenth is 10 -3
|
m*****k
发帖数: 731 | 44 try this case:
s1 = "ABCCCCCCCCCCCCCCCCCCCCCCCCB"
s2 = "ABC"
it seems to me that your way will do a lot of unnecessary computing and
discarding.
0
0 3
0 3 5 => minspan = 5-0+1
0 9 5 => newmin = 9-0+1, discard
10 9 5 => newmin = 10-5+1 discard
10 9 12 => newmin = 12-9+1, update minspan
【在 n********y 的大作中提到】
: 0
: 0 3
: 0 3 5 => minspan = 5-0+1
: 0 9 5 => newmin = 9-0+1, discard
: 10 9 5 => newmin = 10-5+1 discard
: 10 9 12 => newmin = 12-9+1, update minspan
|
n********y
发帖数: 66 | 45 0
0 1
0 1 2 -> minspan = 3
0 1 3 -> newmin = 4 discard
0 1 4 -> newmin = 5 discard
...
second to last
0 1 25 -> newmin = 26 discard
final
0 26 25 -> newmin = 27 discard
【在 m*****k 的大作中提到】
: try this case:
: s1 = "ABCCCCCCCCCCCCCCCCCCCCCCCCB"
: s2 = "ABC"
: it seems to me that your way will do a lot of unnecessary computing and
: discarding.
:
: 0
: 0 3
: 0 3 5 => minspan = 5-0+1
: 0 9 5 => newmin = 9-0+1, discard
|
P********l
发帖数: 452 | |
i**********e
发帖数: 1145 | 47 paul 的方法是 O(N)吗？我怎么觉得像 O(MN）？这是因为每次为了计算字串长度，必须寻找 minimum，所以要遍历 M 次。有人可以解释一下吗？
我想到最直接的优化方法就是保持一个 min heap，能 O(1) 索取 minimum，但是代价就是 insert 和 delete 需要 O(lg M)。总复杂度为 O(N lg M)。
还有值得一提的是，以上的例子小串里没有重复的字母。万一小串是 "AABC" 怎么办呢？以上的方法都不能解决这个情况，只有 han6 的方法似乎比较对的，就是利用两个指针。但是解释得有点复杂，建议看 stormrage 的精简解法（在第9楼）。
http://mitbbs.com/article_t/JobHunting/31731763.html
楼上有人说如果 M 相对 N 很小，可以直接忽略，万一面试官不觉得是这么回事那就完蛋啦。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 p********7 的大作中提到】
: 刚才的算法有问题，不能达到O（N），下面这个应该没问题
: 先遍历一次，记录S2每个char的位置
: s1 = "ADOBECODEBANCBBCAA"
: s2 = "ABC"
: 按顺序记录就行了不用管ABC
: record是一个DOUBLE链表 0，3，5，9，10，12，13，14，15，16，17，18
: 下次遍历的时候用一个hashtable，记录位置，并且记录链表node的指针
: 只用遍历record的位置，并且record最小值
: a b c
: 0 3 5
|
s****e
发帖数: 139 | |
m*****k
发帖数: 731 | 49 给一个字符串s1,和一个小串s2，求算法能在s1中找到包含s2里所有字符的最小子串。
比如，
s1 = "ADOBECODEBANC"
s2 = "ABC"
A: 0,10,
B: 3, 9,
C: 5,12
(0,3,5) length is 5-0
min 0, remove 0, take next one, say 10
(10,3,5) lenth is 10 -3
min 3, remove, take next, 9
(10,9,5) length is 10 - 5
min 5, remove, take next, 12
(10,9,12) lenth is 12 - 9
min 9, remove, no next, done.
shortest is 12 - 9, which is (10,9,12)
【在 D********g 的大作中提到】
: 给一个字符串s1,和一个小串s2，求算法能在s1中找到包含s2里所有字符的最小子串。
: 比如，
: s1 = "ADOBECODEBANC"
: s2 = "ABC"
: 最小子串是 "BANC"
: 要求O(N)的算法。
|
n********y
发帖数: 66 | 50 0
0 3
0 3 5 => minspan = 5-0+1
0 9 5 => newmin = 9-0+1, discard
10 9 5 => newmin = 10-5+1 discard
10 9 12 => newmin = 12-9+1, update minspan
【在 m*****k 的大作中提到】
: 给一个字符串s1,和一个小串s2，求算法能在s1中找到包含s2里所有字符的最小子串。
: 比如，
: s1 = "ADOBECODEBANC"
: s2 = "ABC"
: A: 0,10,
: B: 3, 9,
: C: 5,12
: (0,3,5) length is 5-0
: min 0, remove 0, take next one, say 10
: (10,3,5) lenth is 10 -3
|
|
|
m*****k
发帖数: 731 | 51 try this case:
s1 = "ABCCCCCCCCCCCCCCCCCCCCCCCCB"
s2 = "ABC"
it seems to me that your way will do a lot of unnecessary computing and
discarding.
0
0 3
0 3 5 => minspan = 5-0+1
0 9 5 => newmin = 9-0+1, discard
10 9 5 => newmin = 10-5+1 discard
10 9 12 => newmin = 12-9+1, update minspan
【在 n********y 的大作中提到】
: 0
: 0 3
: 0 3 5 => minspan = 5-0+1
: 0 9 5 => newmin = 9-0+1, discard
: 10 9 5 => newmin = 10-5+1 discard
: 10 9 12 => newmin = 12-9+1, update minspan
|
n********y
发帖数: 66 | 52 0
0 1
0 1 2 -> minspan = 3
0 1 3 -> newmin = 4 discard
0 1 4 -> newmin = 5 discard
...
second to last
0 1 25 -> newmin = 26 discard
final
0 26 25 -> newmin = 27 discard
【在 m*****k 的大作中提到】
: try this case:
: s1 = "ABCCCCCCCCCCCCCCCCCCCCCCCCB"
: s2 = "ABC"
: it seems to me that your way will do a lot of unnecessary computing and
: discarding.
:
: 0
: 0 3
: 0 3 5 => minspan = 5-0+1
: 0 9 5 => newmin = 9-0+1, discard
|
P********l
发帖数: 452 | |
r*******g
发帖数: 1335 | 54 very good post. many thanks.
basically, one solution is O(NlgM) but can not handle duplicates. One
solution is O(N) with additionally two maps.
必须寻找 minimum，所以要遍历 M 次。有人可以解释一下吗？
价就是 insert 和 delete 需要 O(lg M)。总复杂度为 O(N lg M)。
呢？以上的方法都不能解决这个情况，只有 han6 的方法似乎比较对的，就是利用两个
指针。但是解释得有点复杂，建议看 stormrage 的精简解法（在第9楼）。
完蛋啦。
【在 i**********e 的大作中提到】
: paul 的方法是 O(N)吗？我怎么觉得像 O(MN）？这是因为每次为了计算字串长度，必须寻找 minimum，所以要遍历 M 次。有人可以解释一下吗？
: 我想到最直接的优化方法就是保持一个 min heap，能 O(1) 索取 minimum，但是代价就是 insert 和 delete 需要 O(lg M)。总复杂度为 O(N lg M)。
: 还有值得一提的是，以上的例子小串里没有重复的字母。万一小串是 "AABC" 怎么办呢？以上的方法都不能解决这个情况，只有 han6 的方法似乎比较对的，就是利用两个指针。但是解释得有点复杂，建议看 stormrage 的精简解法（在第9楼）。
: http://mitbbs.com/article_t/JobHunting/31731763.html
: 楼上有人说如果 M 相对 N 很小，可以直接忽略，万一面试官不觉得是这么回事那就完蛋啦。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
