forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathKwonNayeon.py
More file actions
53 lines (44 loc) ยท 1.58 KB
/
KwonNayeon.py
File metadata and controls
53 lines (44 loc) ยท 1.58 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
"""
Constraints:
- m == s.length
- n == t.length
- 1 <= m, n <= 10^5
- s and t consist of uppercase and lowercase English letters.
Time Complexity: O(s * t)
- for ๋ฃจํ๋ก s์ ๊ธธ์ด๋งํผ ๋ฐ๋ณต
- while ๋ฃจํ ์์ all() ์กฐ๊ฑด์์ t์ ๊ฐ ๋ฌธ์ ๋น๊ต
- ๋ฐ๋ผ์ O(s * t)
Space Complexity: O(s + t)
- t_counts: O(t)์ ๊ณต๊ฐ
- w_counts: O(s)์ ๊ณต๊ฐ
- ๋ฐ๋ผ์ O(s + t)
ํ์ด๋ฐฉ๋ฒ:
1. Counter๋ก t์ ๋ฌธ์ ๋น๋์ ์ ์ฅ
2. ์ฌ๋ผ์ด๋ฉ ์๋์ฐ๋ก s ํ์:
- high ํฌ์ธํฐ๋ก ์๋์ฐ๋ฅผ ํ์ฅํ๋ฉฐ ํ์ํ ๋ฌธ์ ์ฐพ๊ธฐ
- ํ์ํ ๋ฌธ์๋ฅผ ๋ชจ๋ ์ฐพ์ผ๋ฉด low ํฌ์ธํฐ๋ก ์๋์ฐ ์ถ์
3. ์ต์ ๊ธธ์ด์ ์๋์ฐ ๋ฐํ
๋ฉ๋ชจ:
- ๊ด๋ จ ๋ฌธ์ :
- Two Sum (๋์
๋๋ฆฌ)
- Ransom Note (Counter)
- Longest Substring Without Repeating (์ฌ๋ผ์ด๋ฉ ์๋์ฐ)
- Permutation in String (์ฌ๋ผ์ด๋ฉ ์๋์ฐ + Counter)
- Find All Anagrams in a String (์ฌ๋ผ์ด๋ฉ ์๋์ฐ + Counter)
- 4, 5๋ฒ ๋ฌธ์ ๋จผ์ ํ์ด๋ณด๊ธฐ
"""
class Solution:
def minWindow(self, s: str, t: str) -> str:
t_counts = Counter(t)
w_counts = Counter()
min_low, min_high = 0, len(s)
low = 0
for high in range(len(s)):
w_counts[s[high]] += 1
while all(t_counts[ch] <= w_counts[ch] for ch in t_counts):
if high - low < min_high - min_low:
min_low, min_high = low, high
if s[low] in t_counts:
w_counts[s[low]] -= 1
low += 1
return s[min_low : min_high + 1] if min_high < len(s) else ""