:type s: str :type t: str :rtype: str
(self, s, t)
| 60 | |
| 61 | class Solution(object): |
| 62 | def minWindow(self, s, t): |
| 63 | """ |
| 64 | :type s: str |
| 65 | :type t: str |
| 66 | :rtype: str |
| 67 | """ |
| 68 | |
| 69 | # b = set(t) |
| 70 | b = {} |
| 71 | for i in t: |
| 72 | try: |
| 73 | b[i] += 1 |
| 74 | except: |
| 75 | b[i] = 1 |
| 76 | |
| 77 | a = b.copy() |
| 78 | |
| 79 | # [(mins_index, maxs_index), (mins_index, maxs_index), (mins_index, maxs_index)] |
| 80 | |
| 81 | x = {} |
| 82 | mins = "" |
| 83 | # t_min = 0 |
| 84 | # t_max = 0 |
| 85 | |
| 86 | for i, d in enumerate(s): |
| 87 | if d in b: |
| 88 | try: |
| 89 | x[d].append(i) |
| 90 | except: |
| 91 | x[d] = deque([i], maxlen=b[d]) |
| 92 | |
| 93 | if a.get(d): |
| 94 | a[d] -= 1 |
| 95 | if not a[d]: |
| 96 | a.pop(d) |
| 97 | |
| 98 | if not a: |
| 99 | values = x.values() |
| 100 | if not mins: |
| 101 | |
| 102 | mins = s[min((q[0] for q in values)):max((q[-1] for q in values))+1] |
| 103 | else: |
| 104 | mins = min(mins, s[min((q[0] for q in values)):max((q[-1] for q in values))+1], key=len) |
| 105 | |
| 106 | if a: |
| 107 | return "" |
| 108 | return mins |