Lexi's Leetcode solutions

[Leetcode] Minimum Window Substring 在长string中找包含短string的所有char的substring

Posted on: August 2, 2013

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".

这题说的不清楚,其实T可以有重复字母,比如AAA,那S中必须包括3个A才行。不是包括A就行了。

自己的做法只能cover木有重复字母的情况。思路: 先把T中的每个字母在S中的位置记录下来,生成一个Map<Char, Queue<Index>>。然后像n个pipe一样,每次找到最小的和最大的head,然后算diff(即包括所有queue head的interval的长度)。用diff update resultLength。最后把最小的那个dequeue,然后新的head和max, min比较,update,都是O(1)的时间。这样是O(n) + O(n)。不过解决不了重复字母的问题。尼玛。。好不容易自己想出来一个。。

下次再想想怎么办,或者干脆看答案。

Advertisements
Tags: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: