forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathEgonD3V.py
More file actions
67 lines (53 loc) ยท 1.91 KB
/
EgonD3V.py
File metadata and controls
67 lines (53 loc) ยท 1.91 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
from collections import Counter
from typing import List
from unittest import TestCase, main
class Solution:
def minWindow(self, s: str, t: str) -> str:
return self.solve_two_pointer(s, t)
"""
Runtime: 129 ms (Beats 50.44%)
Time Complexity: O(S)
- ๋ฌธ์์ด s๋ฅผ enumerate๋ก ์ํํ๋๋ฐ O(S)
- ์ํ ํ left๋ฅผ ๊ฐฑ์ ํ๋ while๋ฌธ์์ left๊ฐ 0๋ถํฐ n๊น์ง ๋จ์กฐ์ฆ๊ฐํ๋ฏ๋ก ์ด ์กฐํ๋ O(S)
> O(S) + O(S) ~= O(S)
Memory: 17.32 MB (Beats 32.52%)
Space Complexity: O(S)
- counter ๋ณ์์ ์ด๊ธฐ ํฌ๊ธฐ๋ O(T)
- ๋ฐ๋ณต๋ฌธ์ ์กฐํํ๋ฉฐ counter ๊ฐฑ์ , ์ต์
์ ๊ฒฝ์ฐ s์ ๋ชจ๋ ๋ฌธ์๊ฐ ๋ค๋ฅด๊ณ s == t์ธ ๊ฒฝ์ฐ ์ด๋ฏ๋ก O(S), upper bound
> O(S)
"""
def solve_two_pointer(self, s: str, t: str) -> str:
counter = Counter(t)
missing = len(t)
left = start = end = 0
for right, char in enumerate(s, start=1):
missing -= counter[char] > 0
counter[char] -= 1
if missing == 0:
while left < right and counter[s[left]] < 0:
counter[s[left]] += 1
left += 1
if not end or right - left <= end - start:
start, end = left, right
counter[s[left]] += 1
missing += 1
left += 1
return s[start:end]
class _LeetCodeTestCases(TestCase):
def test_1(self):
s = "ADOBECODEBANC"
t = "ABC"
output = "BANC"
self.assertEqual(Solution.minWindow(Solution(), s, t), output)
def test_2(self):
s = "a"
t = "a"
output = "a"
self.assertEqual(Solution.minWindow(Solution(), s, t), output)
def test_3(self):
s = "a"
t = "aa"
output = ""
self.assertEqual(Solution.minWindow(Solution(), s, t), output)
if __name__ == '__main__':
main()