forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHoonDongKang.ts
More file actions
88 lines (75 loc) ยท 2.53 KB
/
HoonDongKang.ts
File metadata and controls
88 lines (75 loc) ยท 2.53 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
/**
* [Problem]: [76] Minimum Window Substring
* (https://leetcode.com/problems/minimum-window-substring/description/)
*/
function minWindow(s: string, t: string): string {
//์๊ฐ๋ณต์ก๋ O(n)
//๊ณต๊ฐ๋ณต์ก๋ O(n)
function windowFunc(s: string, t: string): string {
let left = 0;
let right = 0;
let s_map = new Map<string, number>();
let t_map = new Map<string, number>();
let minCount = Infinity;
let minStart = 0;
for (const char of t) {
t_map.set(char, (t_map.get(char) || 0) + 1);
}
while (right < s.length) {
let char = s[right];
s_map.set(char, (s_map.get(char) || 0) + 1);
right++;
while (isValid(s_map)) {
if (right - left < minCount) {
minCount = right - left;
minStart = left;
}
let char = s[left];
s_map.set(char, s_map.get(char)! - 1);
left++;
}
}
return minCount === Infinity ? "" : s.slice(minStart, minStart + minCount);
function isValid(map: Map<string, number>): boolean {
for (let i of t_map.keys()) {
if ((map.get(i) || 0) < t_map.get(i)!) return false;
}
return true;
}
}
//์๊ฐ๋ณต์ก๋ O(n)
//๊ณต๊ฐ๋ณต์ก๋ O(n)
function optimizedFunc(s: string, t: string): string {
const map = new Map<string, number>();
let required = t.length;
let left = 0;
let minLen = Infinity;
let minStart = 0;
for (const char of t) {
map.set(char, (map.get(char) || 0) + 1);
}
for (let right = 0; right < s.length; right++) {
const char = s[right];
if (map.has(char)) {
const count = map.get(char)!;
if (0 < count) required--;
map.set(char, count - 1);
}
while (required === 0) {
const char = s[left];
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minStart = left;
}
if (map.has(char)) {
map.set(char, map.get(char)! + 1);
if (map.get(char)! > 0) {
required++;
}
}
left++;
}
}
return minLen === Infinity ? "" : s.slice(minStart, minStart + minLen);
}
}