j********e
发帖数: 1192 | 1 问题如下。搞了个linear的算法，两个指针往后扫那种，实现起来太
复杂了，费了太多时间调试。有简单的O(n)算法么？
Minimum Window Substring
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".
Note:
If there is no such window in S that covers all characters in T, return the
emtpy string "".
If there are multiple such windows, you are guaranteed that there will
always be only one unique minimum window in S. |
p*****2
发帖数: 21240 | 2
今天有时间写一个。
【在 j********e 的大作中提到】
: 问题如下。搞了个linear的算法，两个指针往后扫那种，实现起来太
: 复杂了，费了太多时间调试。有简单的O(n)算法么？
: Minimum Window Substring
: 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".
: Note:
|
p*****2
发帖数: 21240 | 3 def min(S,T):
d1={}
d2={}
for c in T:
if not d1.has_key(c):
d1[c]=0
d1[c]+=1
dq=deque()
count=len(d1)
ans=S
for i in xrange(len(S)):
c=S[i]
if d1.has_key(c):
dq.append(i)
if not d2.has_key(c):
d2[c]=0
d2[c]+=1
if d2[c]==d1[c]:
count-=1
if count==0:
while len(dq)>0 and d2[S[dq[0]]]>d1[S[dq[0]]]:
d2[S[dq[0]]]-=1
dq.popleft()
if dq[-1]-dq[0]+1
ans=S[dq[0]:dq[-1]+1]
return ans |
C***U
发帖数: 2406 | 4 你的O(n)时间的算法 空间也是O(n)吧？
【在 j********e 的大作中提到】
: 问题如下。搞了个linear的算法，两个指针往后扫那种，实现起来太
: 复杂了，费了太多时间调试。有简单的O(n)算法么？
: Minimum Window Substring
: 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".
: Note:
|
j********e
发帖数: 1192 | 5 你想简单了，如果T是AAB，那么要求S对应的substring里包含两个A。
你的算法只适合T没有duplicate字符的情况。
而且memory usage是O(T.size()).
def min(S,T):
d1={}
d2={}
for c in T:
if not d1.has_key(c):
d1[c]=0
d1[c]+=1
dq=deque()
count=len(d1)
ans=S
for i in xrange(len(S)):
c=S[i]
if d1.has_key(c):
dq.append(i)
if not d2.has_key(c):
d2[c]=0
d2[c]+=1
if d2[c]==d1[c]:
count-=1
if count==0:
while len(dq)>0 and d2[S[dq[0]]]>d1[S[dq[0]]]:
d2[S[dq[0]]]-=1
dq.popleft()
if dq[-1]-dq[0]+1
ans=S[dq[0]:dq[-1]+1]
return ans
【在 p*****2 的大作中提到】
: def min(S,T):
: d1={}
: d2={}
:
: for c in T:
: if not d1.has_key(c):
: d1[c]=0
: d1[c]+=1
:
: dq=deque()
|
j********e
发帖数: 1192 | 6 空间上，我用了一个bitmap，256个int，所以应该算O(1)吧。
（btw，如果不算返回的字符串的话).
我的做法类似peking2的，但是用了bitmap替代queue
【在 C***U 的大作中提到】
: 你的O(n)时间的算法 空间也是O(n)吧？
|
p*****2
发帖数: 21240 | 7
are you sure?
【在 j********e 的大作中提到】
: 你想简单了，如果T是AAB，那么要求S对应的substring里包含两个A。
: 你的算法只适合T没有duplicate字符的情况。
: 而且memory usage是O(T.size()).
:
: def min(S,T):
: d1={}
: d2={}
:
: for c in T:
: if not d1.has_key(c):
|
j********e
发帖数: 1192 | 8 不好意思，我看错了，python我读起来还是比较费劲。
【在 p*****2 的大作中提到】
:
: are you sure?
|
w****x
发帖数: 2483 | 9 这题昨天用北京二爷的方法刚做过， 用一个counter记录cover住短字符串的个数并动
态更新，就不用每次去查int rec[256]了，计时花了不到15分钟 |
