Posted on 2022-10-22 19:24
Uriel 閱讀(55)
評論(0) 編輯 收藏 引用 所屬分類:
閑來無事重切Leet Code 、
游標.移動窗口
復雜度O(mn)不曉得能不能貓過，直接想了O(m+n)的
先用字典預處理，判斷s是否一定包含t，是的話維護兩個指針pos_l和pos_r，從開頭掃到結尾，若當區(qū)間已經包含t，則更新最短結果+pos_l右移，否則pos_r右移，注意當pos_r移動到最右端時并不能立刻停止，因為pos_l或許可以繼續(xù)右移，得到更短的答案
因為各種腦殘沒考慮到的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]