forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathseungriyou.py
More file actions
114 lines (94 loc) ยท 4.95 KB
/
seungriyou.py
File metadata and controls
114 lines (94 loc) ยท 4.95 KB
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
# https://leetcode.com/problems/minimum-window-substring/
class Solution:
def minWindow1(self, s: str, t: str) -> str:
"""
[Complexity]
- TC: O(m * k + n) (k = is_included() = len(set(t)))
- SC: O(k) (res ์ ์ธ)
[Approach]
๋ค์๊ณผ ๊ฐ์ counter๋ฅผ ์ ์งํ๋ฉฐ, two pointer๋ก window๋ฅผ ์ด๋ํ๋ฉฐ min window substring์ ํธ๋ํนํ๋ค.
- ์์ฑ ์) t์ ๋ชจ๋ ๋ฌธ์์ ๋ํด ++
- pointer ์ด๋ ์) window์ ํฌํจ๋๋ ๋ฌธ์ ์ค t์ ์ํ๋ ๋ฌธ์์ ๋ํด --
"""
from collections import Counter
# early stop
m, n = len(s), len(t)
if m < n:
return ""
# t์ ๋ํ counter ์์ฑ
counter = Counter(t)
# t์ ๋ชจ๋ ๋ฌธ์๊ฐ window์ ํฌํจ๋๋์ง ํ์ธํ๋ ํจ์
def is_included():
# counter์ ๋ชจ๋ ๊ฐ์ด 0 ์ดํ์ด๋ฉด, t์ ๋ชจ๋ ๋ฌธ์๊ฐ window์ ํฌํจ๋๋ ๊ฒ (์ค๋ณต ํฌํจ)
return all(c <= 0 for c in counter.values())
lo, min_len = 0, 1e6
res = ""
for hi in range(m):
# ํ์ฌ window์ ํฌํจ๋ ๋ฌธ์๋ฅผ counter์ ๋ฐ์
if s[hi] in counter:
counter[s[hi]] -= 1
# t์ ๋ชจ๋ ๋ฌธ์๊ฐ window์ ํฌํจ๋์ด์๋ค๋ฉด(= counter์ ๋ชจ๋ ๊ฐ์ด <= 0์ด๋ฉด),
# counter ๊ฐ์ด ์์ ~ 0์ด ๋ ๋๊น์ง lo ์ฆ๊ฐ์ํค๋ฉด์ (min window๋ฅผ ๊ตฌํด์ผํ๋ฏ๋ก) counter ์
๋ฐ์ดํธ
if is_included():
while True:
# window์ ์ฒซ ๋ฒ์งธ ๋ฌธ์๊ฐ t์ ์ํ๋ ๋ฌธ์๋ผ๋ฉด
if s[lo] in counter:
# counter์์์ ๊ฐ์ด 0์ด๋ฉด, ๋์ด์ lo๋ฅผ ์ค๋ฅธ์ชฝ์ผ๋ก ์ค์ผ ์ ์์
if counter[s[lo]] == 0:
break
# coutner์์์ ๊ฐ์ด ์์๋ผ๋ฉด, lo๋ฅผ ์ค๋ฅธ์ชฝ์ผ๋ก ์ค์ผ ์ ์์ผ๋ฏ๋ก counter ๋ฐ์
else:
counter[s[lo]] += 1
# lo๋ฅผ ์ค๋ฅธ์ชฝ์ผ๋ก ํ ์นธ ์ด๋
lo += 1
# (1) t์ ๋ชจ๋ ๋ฌธ์๊ฐ window์ ํฌํจ๋์ด ์๊ณ (2) ํ์ฌ window์ length๊ฐ min_len ๋ณด๋ค ์๋ค๋ฉด
# window substring ์
๋ฐ์ดํธ
if is_included() and (new_len := hi - lo + 1) < min_len:
min_len = new_len
res = s[lo:hi + 1]
return res
def minWindow(self, s: str, t: str) -> str:
"""
[Complexity]
- TC: O(m + n)
- SC: O(k)
[Approach]
1) ์์ ํ์ด์์ is_included()๋ฅผ ์คํํ๋ ๋ฐ์ O(k)์ด ์์๋๋ฏ๋ก,
(t์ ์ํ๋ ๋ฌธ์ ์ค, ์์ง window์ ๋ชจ๋ ํฌํจ๋์ง ์์ ๋ฌธ์ ์ข
๋ฅ ๊ฐ์)๋ฅผ ํธ๋ํนํ๋ ๋ณ์ remains๋ฅผ ์ด์ฉํ์ฌ ์ต์ ํ ํ๋ค.
์ฆ, remains == 0์ด๋ผ๋ฉด is_included()์ธ ๊ฒ๊ณผ ๋์ผํ๋ค.
2) ๋ฐ๋ณต๋ฌธ ์์์ ๋ฌธ์์ด ์ฌ๋ผ์ด์ฑ์ผ๋ก res๋ฅผ ์
๋ฐ์ดํธ ํ ๋ ์ถ๊ฐ์ ์ธ ๋ณต์ก๋๊ฐ ์์๋๋ค.
๋ฐ๋ผ์ min window์ ๋ํ pointer์ธ min_lo, min_hi๋ง ํธ๋ํนํ๊ณ , return ๋ฌธ์์ ๋ฌธ์์ด ์ฌ๋ผ์ด์ฑ์ผ๋ก ๋ฐํํ๋ค.
๋จ, min window substring์ด ์กด์ฌํ์ง ์๋๋ค๋ฉด ๊ฒฐ๊ณผ๊ฐ ๋น ๋ฌธ์์ด์ด ๋ ์ ์์ผ๋ฏ๋ก, min_lo ~ min_hi - 1 ๋ฒ์๋ฅผ ๋ฐํํ๋๋ก ํ๋ค.
"""
from collections import Counter
# early stop
m, n = len(s), len(t)
if m < n:
return ""
# t์ ๋ํ counter ์์ฑ
counter = Counter(t)
# counter์ ๊ฐ์ ๋ชจ๋ ํ์ธํ๋ is_include() ์ต์ ํ
remains = len(counter) # t์ ์ํ๋ ๋ฌธ์ ์ค, ์์ง window์ ๋ชจ๋ ํฌํจ๋์ง ์์ ๋ฌธ์ ์ข
๋ฅ ๊ฐ์
lo = min_lo = min_hi = 0
min_len = m + 1
for hi in range(m):
# ํ์ฌ window์ ํฌํจ๋ ๋ฌธ์๋ฅผ counter์ ๋ฐ์
if s[hi] in counter:
counter[s[hi]] -= 1
# ํ์ฌ window์ ํด๋น ๋ฌธ์๊ฐ t์ ์กด์ฌํ๋ ๊ฐ์๋งํผ ๋ค์ด์์๋ค๋ฉด, remains--
if counter[s[hi]] == 0:
remains -= 1
# t์ ๋ชจ๋ ๋ฌธ์๊ฐ window์ ํฌํจ๋์ด์๋ ๋์ lo ์ด๋
while not remains:
# ์ต์ ๊ธธ์ด window substring ๊ฐฑ์
if (new_len := hi - lo + 1) < min_len:
min_len, min_lo, min_hi = new_len, lo, hi + 1
# lo ์ด๋ ์ , counter ์
๋ฐ์ดํธ
if s[lo] in counter:
counter[s[lo]] += 1
# counter์ ๊ฐ์ด 0 ์ด๊ณผ๊ฐ ๋๋ค๋ฉด, ๋์ด์ window์ ํด๋น ๋ฌธ์๊ฐ ๋ชจ๋ ๋ค์ด์์ง ์๋ค๋ ๊ฒ์ด๋ฏ๋ก remains++
if counter[s[lo]] > 0:
remains += 1
# lo๋ฅผ ์ค๋ฅธ์ชฝ์ผ๋ก ํ ์นธ ์ด๋
lo += 1
return s[min_lo:min_hi]