forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathtaurus09318976.py
More file actions
103 lines (77 loc) ยท 3.66 KB
/
taurus09318976.py
File metadata and controls
103 lines (77 loc) ยท 3.66 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
'''
๋ฌธ์ ์ ์๋
์ด ๋ฌธ์ ๋ ๋ฌธ์์ด s์์ ๋ฌธ์์ด t์ ๋ชจ๋ ๋ฌธ์(์ค๋ณต ํฌํจ)๋ฅผ ํฌํจํ๋ ๊ฐ์ฅ ์งง์ ๋ถ๋ถ ๋ฌธ์์ด์ ์ฐพ๋ ๋ฌธ์ ์.
ํต์ฌ ํฌ์ธํธ:
1) t์ ๋ชจ๋ ๋ฌธ์๊ฐ ํฌํจ๋์ด์ผ ํจ (์ค๋ณต ๊ฐ์๋ ๋ง์์ผ ํจ)
2) ๊ฐ์ฅ ์งง์ ๊ธธ์ด์ ๋ถ๋ถ ๋ฌธ์์ด์ ์ฐพ์์ผ ํจ
3) ์ฐ์๋ ๋ถ๋ถ ๋ฌธ์์ด์ด์ด์ผ ํจ
ํด๊ฒฐ ๋ฐฉ๋ฒ
์ฌ๋ผ์ด๋ฉ ์๋์ฐ + ํฌ ํฌ์ธํฐ ๊ธฐ๋ฒ์ ์ฌ์ฉํจ:
์ค๋ฅธ์ชฝ ํฌ์ธํฐ๋ก ์๋์ฐ๋ฅผ ํ์ฅํ์ฌ ์กฐ๊ฑด์ ๋ง์กฑ์ํด
์กฐ๊ฑด์ ๋ง์กฑํ๋ฉด ์ผ์ชฝ ํฌ์ธํฐ๋ก ์๋์ฐ๋ฅผ ์ถ์ํ์ฌ ์ต์ ๊ธธ์ด ์ฐพ๊ธฐ
ํด์๋งต์ผ๋ก ๋ฌธ์ ๊ฐ์๋ฅผ ํจ์จ์ ์ผ๋ก ๊ด๋ฆฌ
Example 1์ ๊ฒฝ์ฐ๋ฅผ ๋ณด๋ฉด,
Input: s = "ADOBECODEBANC", t = "ABC"
์คํ ๊ณผ์ :
t_count: {'A':1, 'B':1, 'C':1}, required = 3
์๋์ฐ ํ์ฅ: right ํฌ์ธํฐ๋ก "ADOBEC"๊น์ง ํ์ฅ โ ์กฐ๊ฑด ๋ง์กฑ
์๋์ฐ ์ถ์: left ํฌ์ธํฐ๋ก "ODEBANC" โ "BANC"๊น์ง ์ถ์
์ต์ข
๊ฒฐ๊ณผ: "BANC" (๊ธธ์ด 4)
Output: "BANC"
์๊ฐ ๋ณต์ก๋: O(|s| + |t|)
๊ฐ ๋ฌธ์๊ฐ ์ต๋ 2๋ฒ ๋ฐฉ๋ฌธ๋จ (right ํฌ์ธํฐ๋ก 1๋ฒ, left ํฌ์ธํฐ๋ก 1๋ฒ)
t๋ฅผ ํ ๋ฒ ์ํํ์ฌ ํด์๋งต ์์ฑ: O(|t|)
์ ์ฒด์ ์ผ๋ก ์ ํ ์๊ฐ ๋ณต์ก๋
๊ณต๊ฐ ๋ณต์ก๋: O(|s| + |t|)
t_count ํด์๋งต: O(|t|)
window_counts ํด์๋งต: ์ต๋ O(|s|)
๊ธฐํ ๋ณ์๋ค: O(1)
'''
class Solution:
def minWindow(self, s: str, t: str) -> str:
# t๊ฐ ๋น ๋ฌธ์์ด์ด๋ฉด ๋น ๋ฌธ์์ด ๋ฐํ
if not t:
return ""
# t์ ๊ฐ ๋ฌธ์ ๊ฐ์๋ฅผ ์ ์ฅํ๋ ํด์๋งต
t_count = {}
for char in t:
t_count[char] = t_count.get(char, 0) + 1
# ์กฐ๊ฑด์ ๋ง์กฑํ๊ธฐ ์ํด ํ์ํ ๊ณ ์ ๋ฌธ์์ ๊ฐ์
required = len(t_count)
# ์ฌ๋ผ์ด๋ฉ ์๋์ฐ์ ์ผ์ชฝ, ์ค๋ฅธ์ชฝ ํฌ์ธํฐ์ ์กฐ๊ฑด์ ๋ง์กฑํ๋ ๋ฌธ์ ๊ฐ์ ์ด๊ธฐํ
left = 0
right = 0
# ํ์ฌ ์๋์ฐ์์ ์กฐ๊ฑด์ ๋ง์กฑํ๋ ๋ฌธ์์ ๊ฐ์
formed = 0
# ํ์ฌ ์๋์ฐ์ ๋ฌธ์ ๊ฐ์๋ฅผ ์ ์ฅํ๋ ํด์๋งต
window_counts = {}
# ๊ฒฐ๊ณผ๋ฅผ ์ ์ฅํ ๋ณ์๋ค
min_len = float('inf')
min_left = 0
min_right = 0
# ์ค๋ฅธ์ชฝ ํฌ์ธํฐ๋ก ์๋์ฐ ํ์ฅ
while right < len(s):
# ์ค๋ฅธ์ชฝ ๋ฌธ์๋ฅผ ์๋์ฐ์ ์ถ๊ฐ
char = s[right]
window_counts[char] = window_counts.get(char, 0) + 1
# ํ์ฌ ๋ฌธ์์ ๊ฐ์๊ฐ t์์ ์๊ตฌํ๋ ๊ฐ์์ ๊ฐ์์ง๋ฉด formed์ 1์ ๋ํจ
if char in t_count and window_counts[char] == t_count[char]:
formed += 1
# ๋ชจ๋ ๋ฌธ์์ ์กฐ๊ฑด์ด ๋ง์กฑ๋๋ฉด ์ผ์ชฝ ํฌ์ธํฐ๋ก ์๋์ฐ๋ฅผ ์ต์ํ ์๋
while left <= right and formed == required:
char = s[left]
# ํ์ฌ ์๋์ฐ๊ฐ ์ง๊ธ๊น์ง์ ์ต์ ๊ธธ์ด๋ณด๋ค ์์ผ๋ฉด ๊ฒฐ๊ณผ ์
๋ฐ์ดํธ
if right - left + 1 < min_len:
min_len = right - left + 1
min_left = left
min_right = right
# ์ผ์ชฝ ๋ฌธ์๋ฅผ ์ ๊ฑฐํ๊ณ , ์กฐ๊ฑด์ ๋ง์กฑํ์ง ์๊ฒ ๋๋ฉด formed์์ 1์ ๋บ
window_counts[char] -= 1
if char in t_count and window_counts[char] < t_count[char]:
formed -= 1
# ์ผ์ชฝ ํฌ์ธํฐ ์ด๋
left += 1
# ์ค๋ฅธ์ชฝ ํฌ์ธํฐ ์ด๋
right += 1
# ๊ฒฐ๊ณผ ๋ฐํ
return "" if min_len == float('inf') else s[min_left:min_right + 1]