forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmmyeon.ts
More file actions
69 lines (56 loc) ยท 2.13 KB
/
mmyeon.ts
File metadata and controls
69 lines (56 loc) ยท 2.13 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
/**
* @link https://leetcode.com/problems/minimum-window-substring/description/
* ์ ๊ทผ ๋ฐฉ๋ฒ : 2๊ฐ์ ํฌ์ธํฐ ํ์ฉํด์ ์ฌ๋ผ์ด๋ฉ ์๋์ฐ ๋ฐฉ์ ์ฌ์ฉ
* - t์ ๋ฌธ์๋ฅผ ๋งต์ ์ ์ฅํด์ ๊ฐ์ ๊ธฐ๋ก
* - right ํฌ์ธํฐ๋ก t์ ๋ชจ๋ ๋ฌธ์ ํฌํจํ ๋๊น์ง ์๋์ฐ ํ์ฅ
* - ๋ชจ๋ ๋ฌธ์ ํฌํจํ๋ฉด, left ํฌ์ธํฐ๋ก ์ต์ ์๋์ฐ ์ฐพ์ ๋๊น์ง ์๋์ฐ ์ถ์
* - 'ํ์ฅ => ์ถ์ => ์ต์ ์๋์ฐ ์
๋ฐ์ดํธ' ์ด ๊ณผ์ ์ ๋ฐ๋ณต
*
* ์๊ฐ๋ณต์ก๋ : O(n)
* - n์ s์ ๊ธธ์ด, ๊ฐ ๋ฌธ์ ์ต๋ 2ํ ๋ฐฉ๋ฌธ (ํ์ฅ + ์ถ์)
*
* ๊ณต๊ฐ๋ณต์ก๋ : O(n)
* - ์ต์
์ ๊ฒฝ์ฐ, ์๋์ฐ์ s์ ๋ชจ๋ ๋ฌธ์๊ฐ ์ ์ฅ๋จ
*/
function minWindow(s: string, t: string): string {
const targetCharCount = new Map<string, number>();
// t์ ๋ฌธ์ ๊ฐ์ ์นด์ดํธ
for (const char of t) {
targetCharCount.set(char, (targetCharCount.get(char) ?? 0) + 1);
}
const requiredUniqueChars = targetCharCount.size;
let matchedUniqueChars = 0;
const windowCharCount = new Map<string, number>();
let minWindow = "";
let minWindowLength = Infinity;
let left = 0,
right = 0;
while (right < s.length) {
const char = s[right];
windowCharCount.set(char, (windowCharCount.get(char) ?? 0) + 1);
// t์ ์ํ๋ ๋ฌธ์์ด๋ฉด์, ๋ฌธ์ ๊ฐ์๊ฐ ๊ฐ์ ๊ฒฝ์ฐ
if (
targetCharCount.has(char) &&
targetCharCount.get(char) === windowCharCount.get(char)
)
matchedUniqueChars++;
while (matchedUniqueChars === requiredUniqueChars) {
const windowLength = right - left + 1;
// ์ต์ ์๋์ฐ ์
๋ฐ์ดํธ
if (windowLength < minWindowLength) {
minWindowLength = windowLength;
minWindow = s.substring(left, right + 1);
}
const leftChar = s[left];
windowCharCount.set(leftChar, windowCharCount.get(leftChar)! - 1);
//์ถ์๋ก ์๋์ฐ ๋ด์ t๋ฌธ์๊ฐ ๊ฐ์ํ์ผ๋ฉด matchedUniqueChars ๊ฐ์
if (windowCharCount.get(leftChar)! < targetCharCount.get(leftChar)!)
matchedUniqueChars--;
// ์๋์ฐ ์ถ์
left++;
}
// ์๋์ฐ ํ์ฅ
right++;
}
return minWindow;
}