滑动窗口解决字符串问题
题目
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
说明
- 如果 S 中不存这样的子串，则返回空字符串
""。
- 如果 S 中存在这样的子串，我们保证它是唯一的答案。
示例
| 输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
|
考察知识点
滑动窗口、hashmap、字符串问题
核心思想
step 1
建立一个可以容纳ASCII的字典mem，然后记录 t 中元素出现的次数。 mem可以理解成t中字母等待确认的次数，在s中出现一次，就减一。t_len记录了t中的字符个数。minL 和 minL 分别是最新窗口的左边缘和右边缘，l 为滑动窗口左边缘。
| mem = Counter(t)
t_len = len(t)
minL, minR = 0, float('inf')
l = 0
|
step 2
遍历s，设置循环下标r为滑动窗口右边缘，将字典mem中的c元素减一，如果s中的元素在t中出现过，记录此时的t_len = len(t)-1。当t_len==0时，说明此时t中的元素在s中都出现了，我们此时要进入下一步判断。
| for r, c in enumerate(s):
if mem[c] > 0:
t_len -= 1
mem[c] -= 1
|
step 3
判断mem中s[l]是不是小于0，如果是的话，说明t中不应该包含s[l]，所以我们需要将它剔除出去（也就是mem[s[l++]]++）。
| if t_len == 0:
while mem < 0: # 判断mem中s是不是小于0，如果是的话，说明t中不应该包含s，就要把滑动窗口右移，所以我们需要将它剔除出去（也就是mem++）。
mem += 1 # mem对应值归零
l += 1 # 滑动窗口右移
|
step 4
完成滑动窗口右移，找到最前面的一个t字符之后，我们记录此时的l和r为寻找得到的最小窗口。接着我们需要继续找符合条件的位置，我们将l++并且t_len++，将s[l]再加入到mem中去，这样我们就将窗口向右滑动一步，过掉这个t包含字符，寻找下一个窗口。
| if t_len == 0:
while mem[s[l]] < 0:
mem[s[l]] += 1
l += 1
if r - l < minR - minL:
minL, minR = l, r
mem[s[l]] += 1
t_len += 1
l += 1
|
python版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution:
def minWindow(self, s: 'str', t: 'str') -> 'str':
from collections import defaultdict
lookup = defaultdict(int)
for c in t:
lookup[c] += 1
start = 0
end = 0
min_len = float("inf")
counter = len(t)
res = ""
while end < len(s):
if lookup[s[end]] > 0:
counter -= 1
lookup[s[end]] -= 1
end += 1
while counter == 0:
if min_len > end - start:
min_len = end - start
res = s[start:end]
if lookup[s[start]] == 0:
counter += 1
lookup[s[start]] += 1
start += 1
return res
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| class Solution:
def minWindow(self, s: str, t: str) -> str:
d = {}
repeat_statistis = {}
check_flage = False
min_length = 1000000
min_str = ""
for i in t:
if i in repeat_statistis:
repeat_statistis[i] += 1
else:
repeat_statistis[i] = 1
if len(s) < len(t):
return ""
if len(s) == len(t):
check_flage = True
for i in t:
if i not in s:
check_flage = False
if check_flage:
return s
for i in range(len(s)):
if s[i] in t:
check_flage = True
d[s[i]] = i
tmp_d = dict((v,k) for k,v in d.items())
right_flag = min(tmp_d)
left_flag = max(tmp_d)
sub_str = s[right_flag:left_flag+1]
tmp_sub_str = sub_str
for j in t:
if j not in tmp_sub_str:
check_flage = False
break
else:
tmp_sub_str = list(tmp_sub_str)
tmp_sub_str.remove(j)
tmp_sub_str = "".join(tmp_sub_str)
if check_flage:
if (left_flag-right_flag) < min_length:
min_str = sub_str
min_length = left_flag-right_flag
return min_str
"""
S = "aaflslflsldkalskaaa"
T = "aaa"
Answer = "aaa" # 无法通过这个测试样例 不能以输入样例来控制滑动窗口
if __name__ == "__main__":
solution = Solution()
print(solution.minWindow(S, T))
"""
|
不能以输入样例来控制滑动窗口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| from collections import Counter
class Solution:
def minWindow(self, s, t):
mem = Counter(t)
t_len = len(t)
minL, minR = 0, float('inf')
l = 0
for r, c in enumerate(s):
if mem[c] > 0:
t_len -= 1
mem[c] -= 1
if t_len == 0:
while mem[s[l]] < 0:
mem[s[l]] += 1
l += 1
if r - l < minR - minL:
minL, minR = l, r
mem[s[l]] += 1
t_len += 1
l += 1
return '' if minR == float('inf') else s[minL:minR+1]
print("leet code accept!!!")
S = ["ADOBECODEBANC", "aa", "bbaa", "aaflslflsldkalskaaa"]
T = ["ABC", "aa", "aba", "aaa"]
Answer = ["BANC", "aa", "baa", "aaa"]
if __name__ == "__main__":
solution = Solution()
for i in range(len(S)):
result = solution.minWindow(S[i], T[i])
print(result==Answer[i])
|
有效语法糖
1、from collections import Counter 是一个计数器工具提供快速和方便的计数。
使用方法: 参考链接
| c = Counter()
c = Counter('gallahad')
c = Counter({'a': 4, 'b': 2})
c = Counter(a=4, b=2)
|
2、minL, minR = 0, float('inf') 设置正无穷。
使用方法
| >>> a = float('inf')
>>> b = 0
>>> print(a>b)
>>> print(a<b)
True
False
|