U*********y
发帖数: 54 | 1 Given a string S and a string T, find the minimum window in S which will
contain all the characters in T IN THE ORDER AS IT APPEARS IN T in
complexity O(n).
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is NOT "BANC", but "ADOBEC" | l*********u
发帖数: 19053 | 2 只能单向扫一遍S吧。坐等更好方法。
【在 U*********y 的大作中提到】
: Given a string S and a string T, find the minimum window in S which will
: contain all the characters in T IN THE ORDER AS IT APPEARS IN T in
: complexity O(n).
: S = "ADOBECODEBANC"
: T = "ABC"
: Minimum window is NOT "BANC", but "ADOBEC"
| U*********y
发帖数: 54 | 3 发现是EPI的12.15。看了下EPI的解法觉得有问题：在成功扫出来一个range之后，接下
来扫貌似都没有enforce ordering.
【在 l*********u 的大作中提到】
: 只能单向扫一遍S吧。坐等更好方法。
| g*********e
发帖数: 14401 | | d******g
发帖数: 38 | 5 等价于找等于T的并且在S中对应substring最短的LCS，不可能O(n)吧
【在 U*********y 的大作中提到】
: Given a string S and a string T, find the minimum window in S which will
: contain all the characters in T IN THE ORDER AS IT APPEARS IN T in
: complexity O(n).
: S = "ADOBECODEBANC"
: T = "ABC"
: Minimum window is NOT "BANC", but "ADOBEC"
| z****8
发帖数: 7 | 6 T没有重复字母应该可以O(n), 有重复的话, 每次更新，需要找最小index | d******g
发帖数: 38 | 7 删除S中不属于T的字符得到S'，match T with S',O(m+n)
【在 d******g 的大作中提到】
: 等价于找等于T的并且在S中对应substring最短的LCS，不可能O(n)吧
| l*********8
发帖数: 4642 | 8 S = "ABBC"
B = "ABC"
怎么办？
【在 d******g 的大作中提到】
: 删除S中不属于T的字符得到S'，match T with S',O(m+n)
| p*****3
发帖数: 488 | 9 先build reverse index lists, 然后再linear scan multiple lists | d******g
发帖数: 38 | 10 嗯，这个办法不对
【在 l*********8 的大作中提到】
: S = "ABBC"
: B = "ABC"
: 怎么办？
| w********s
发帖数: 1570 | 11 记录pattern中所有字母在原来string的位置
A:0,10
B:3,9
C:5,12
ABC的话，从A开始取出0，找到B开始第一个>0的位置:3，找到C>3的第一个位置5
[0-5]成为一个window
pop掉A:0后
A:10
B:3,9
C:5,12
然后A=10，B中3<10, pop掉，9<10, pop掉，没有元素了，结束。
因为每次循环总能pop掉至少1个元素，总共有n个元素，所以是O(n)
【在 U*********y 的大作中提到】
: Given a string S and a string T, find the minimum window in S which will
: contain all the characters in T IN THE ORDER AS IT APPEARS IN T in
: complexity O(n).
: S = "ADOBECODEBANC"
: T = "ABC"
: Minimum window is NOT "BANC", but "ADOBEC"
| w*****d
发帖数: 105 | 12 我觉得你的算法复杂度应该是O(S*T)，例如：S="AAAAAAAAABC", T="ABC";
每次pop一个A的index，都要进行B和C的检查，总共需要(len(S)-2)*len(T)次计算。
不过我认为这个算法已经是目前最好的了。
我怀疑是否存在O(N)的算法。
【在 w********s 的大作中提到】
: 记录pattern中所有字母在原来string的位置
: A:0,10
: B:3,9
: C:5,12
: ABC的话，从A开始取出0，找到B开始第一个>0的位置:3，找到C>3的第一个位置5
: [0-5]成为一个window
: pop掉A:0后
: A:10
: B:3,9
: C:5,12
| p**o
发帖数: 3409 | 13 (Please use monospaced font to read)
Example:
i: 0 1 2 3 4 5 6 7 8 9
S0: a a b x c a b x c b
T0: a b c b
expected output: [5,10)
n=len(S0), m=len(T0)
Collect indices in S0: O(n) time
a: 0 1 5
b: 2 6 9
c: 4 8
I wanted to use dynamic programming,
but I did not find any optimal substructure.
So I chose to backtrack on these indices instead.
T0: a b c b
i: 0 1 2 3 4 5 6 7 8 9
S0: a a b x c a b x c b
S1: a _ b _ c _ b _ _ _ -> [0,7)
S2: a _ b _ c _ _ _ _ b -> [0,10)
S3: a _ b _ _ _ _ _ c b -> [0,10)
S4: a _ _ _ _ _ b _ c b -> [0,10)
S5: _ a b _ c _ b _ _ _ -> [1,7)
S6: _ a b _ c _ _ _ _ b -> [1,10)
S7: _ a b _ _ _ _ _ c b -> [1,10)
S8: _ a _ _ _ _ b _ c b -> [1,10)
S9: _ _ _ _ _ a b _ c b -> [5,10) best
Compare across S1..S9 we pick S9.
But do we really have to do this comparison at this final stage?
No. Note that in solutions S1..S4 where the index of 'a' is 0,
when solution S1 is found, we don't need to explore S2..S4 at all.
Similarly, in solutions S5..S8 where the index of 'a' is 1,
once S5 is found, we don't need to explore S6..S8 any more.
The greedy principle applies here.
So in the end, we only need to compare S1, S5, S9.
i: 0 1 2 3 4 5 6 7 8 9
S1: a _ b _ c _ b _ _ _ -> [0,7)
S5: _ a b _ c _ b _ _ _ -> [1,7)
S9: _ _ _ _ _ a b _ c b -> [5,10) best
def greedy (s_indices, s, t, si_begin, tj):
if tj >= len(t):
return si_begin
for si in s_indices[t[tj]]:
if si >= si_begin:
return greedy (s_indices, s, t, si+1, tj+1)
def min_win_subs (s, t):
tset = set(t)
s_indices = dict()
for i, c in enumerate(s):
if c in tset:
s_indices.setdefault(c, []).append(i)
min_win_size = 999999
for si_begin in s_indices[t[0]]:
si_end = greedy (s_indices, s, t, si_begin+1, 1)
if si_end is None: continue
if si_end - si_begin < min_win_size:
si_min_begin = si_begin
si_min_end = si_end
min_win_size = si_end - si_begin
return si_min_begin, si_min_end
if __name__ == '__main__':
print(min_win_subs('aabxcabxcb', 'abcb')) # [5,10) |
|
