Posted on 2022-10-22 19:24
Uriel 阅读(36)
评论(0) 编辑 收藏 引用 所属分类:
闲来无事重切Leet Code 、
游标.移动窗口
复杂度O(mn)不晓得能不能猫过，直接想了O(m+n)的
先用字典预处理，判断s是否一定包含t，是的话维护两个指针pos_l和pos_r，从开头扫到结尾，若当区间已经包含t，则更新最短结果+pos_l右移，否则pos_r右移，注意当pos_r移动到最右端时并不能立刻停止，因为pos_l或许可以继续右移，得到更短的答案
因为各种脑残没考虑到的case WA了7次才过。。。
1 #76
2 #Runtime: 302 ms
3 #Memory Usage: 14 MB
4
5 class Solution(object):
6 def minWindow(self, s, t):
7 """
8 :type s: str
9 :type t: str
10 :rtype: str
11 """
12 dict_s ={}
13 for i in s:
14 if i not in dict_s:
15 dict_s[i] = 1
16 else:
17 dict_s[i] += 1
18 dict_t ={}
19 for i in t:
20 if i not in dict_t:
21 dict_t[i] = 1
22 else:
23 dict_t[i] += 1
24 if i not in dict_s:
25 return ""
26 if dict_s[i] < dict_t[i]:
27 return ""
28 pos_l = 0
29 pos_r = 0
30 tp_len_t = len(t)
31 ans_l = 0
32 ans_r = len(s)
33 min_len = len(s)
34 while pos_r < len(s) or tp_len_t <= 0:
35
36 if tp_len_t > 0:
37 if s[pos_r] in dict_t:
38 dict_t[s[pos_r]] -= 1
39 if dict_t[s[pos_r]] >= 0:
40 tp_len_t -= 1
41 pos_r += 1
42 else:
43 if min_len > pos_r - pos_l:
44 ans_l = pos_l
45 ans_r = pos_r
46 min_len = ans_r - ans_l
47 if s[pos_l] in dict_t:
48 dict_t[s[pos_l]] += 1
49 if dict_t[s[pos_l]] > 0:
50 tp_len_t += 1
51 pos_l += 1
52
53 return s[ans_l : ans_r]