forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathYoungSeok-Choi.java
More file actions
104 lines (86 loc) ยท 3.41 KB
/
YoungSeok-Choi.java
File metadata and controls
104 lines (86 loc) ยท 3.41 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
101
102
103
104
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class Solution {
public String minWindow(String s, String t) {
if (s.length() < t.length()) {
return "";
}
Map<Character, Integer> charCount = new HashMap<>();
for (char ch : t.toCharArray()) {
charCount.put(ch, charCount.getOrDefault(ch, 0) + 1);
}
int targetCharsRemaining = t.length();
int[] minWindow = { 0, Integer.MAX_VALUE };
int startIndex = 0;
for (int endIndex = 0; endIndex < s.length(); endIndex++) {
char ch = s.charAt(endIndex);
if (charCount.containsKey(ch) && charCount.get(ch) > 0) {
targetCharsRemaining--;
}
charCount.put(ch, charCount.getOrDefault(ch, 0) - 1);
if (targetCharsRemaining == 0) {
while (true) {
char charAtStart = s.charAt(startIndex);
if (charCount.containsKey(charAtStart) && charCount.get(charAtStart) == 0) {
break;
}
charCount.put(charAtStart, charCount.getOrDefault(charAtStart, 0) + 1);
startIndex++;
}
if (endIndex - startIndex < minWindow[1] - minWindow[0]) {
minWindow[0] = startIndex;
minWindow[1] = endIndex;
}
charCount.put(s.charAt(startIndex), charCount.getOrDefault(s.charAt(startIndex), 0) + 1);
targetCharsRemaining++;
startIndex++;
}
}
return minWindow[1] >= s.length() ? "" : s.substring(minWindow[0], minWindow[1] + 1);
}
}
class WrongSolution { // ์๊ณ ๋ฆฌ์ฆ์ ๋ง์ง๋ง ์๊ฐ์ด๊ณผ ๋ฐ์... O(n)์ sliding window ๋ฐฉ์์ผ๋ก ํ์ด์ผ ํ๋ ๋ฌธ์ ..
public String minWindow(String s, String t) {
Map<Character, Integer> targetMap = new HashMap<>();
List<Integer> candidates = new ArrayList<>();
for (char c : t.toCharArray()) {
targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
}
String minStr = null;
for (int i = 0; i < s.length(); i++) {
if (targetMap.containsKey(s.charAt(i))) {
candidates.add(i);
}
}
int size = candidates.size();
while (size > 0) {
Map<Character, Integer> windowMap = new HashMap<>(targetMap);
int targetCnt = t.length();
int startIdx = candidates.remove(0);
int endIdx = -999;
for (int i = startIdx; i < s.length(); i++) {
char at = s.charAt(i);
if (windowMap.containsKey(at) && windowMap.get(at) > 0) {
windowMap.put(at, windowMap.get(at) - 1);
targetCnt--;
}
if (targetCnt == 0) {
endIdx = i + 1;
break;
}
}
if (targetCnt == 0) {
if (minStr == null) {
minStr = s.substring(startIdx, endIdx);
} else {
int prevSize = minStr.length();
minStr = prevSize < Math.abs(endIdx - startIdx) ? minStr : s.substring(startIdx, endIdx);
}
}
size--;
}
return minStr == null ? "" : minStr;
}
}