-
-
Notifications
You must be signed in to change notification settings - Fork 300
/
30.java
268 lines (259 loc) · 9.66 KB
/
30.java
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
__________________________________________________________________________________________________
4ms
class Solution {
private Map<String, Integer> map;
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<>();
int n = s.length();
int m = words.length;
if(n == 0 || m == 0){
return res;
}
int len = words[0].length();
int window = len * m;
if(n < window){
return res;
}
map = new HashMap<>();
for (String word : words) {
map.put(word, map.getOrDefault(word, 0) + 1);
}
for(int i = 0; i < len; i++){
for(int j = i; j < n - window + 1; j += len){
int k;
Map<String, Integer> curMap = new HashMap<>();
for(k = m - 1; k >= 0; k--){
String temp = s.substring(j + k * len, j + (k + 1) * len);
if(!map.containsKey(temp)){
j += k * len;
break;
}
curMap.put(temp, curMap.getOrDefault(temp, 0) + 1);
if(curMap.get(temp) > map.get(temp)){
j += k * len;
break;
}
}
if(k < 0){
res.add(j);
}
}
}
return res;
}
}
__________________________________________________________________________________________________
5ms
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
int N = s.length();
List<Integer> indexes = new ArrayList<Integer>(s.length());
if (words.length == 0) {
return indexes;
}
int M = words[0].length();
if (N < M * words.length) {
return indexes;
}
int last = N - M + 1;
//map each string in words array to some index and compute target counters
Map<String, Integer> mapping = new HashMap<String, Integer>(words.length);
int [][] table = new int[2][words.length];
int failures = 0, index = 0;
for (int i = 0; i < words.length; ++i) {
Integer mapped = mapping.get(words[i]);
if (mapped == null) {
++failures;
mapping.put(words[i], index);
mapped = index++;
}
++table[0][mapped];
}
//find all occurrences at string S and map them to their current integer, -1 means no such string is in words array
int [] smapping = new int[last];
for (int i = 0; i < last; ++i) {
String section = s.substring(i, i + M);
Integer mapped = mapping.get(section);
if (mapped == null) {
smapping[i] = -1;
} else {
smapping[i] = mapped;
}
}
//fix the number of linear scans
for (int i = 0; i < M; ++i) {
//reset scan variables
int currentFailures = failures; //number of current mismatches
int left = i, right = i;
Arrays.fill(table[1], 0);
//here, simple solve the minimum-window-substring problem
while (right < last) {
while (currentFailures > 0 && right < last) {
int target = smapping[right];
if (target != -1 && ++table[1][target] == table[0][target]) {
--currentFailures;
}
right += M;
}
while (currentFailures == 0 && left < right) {
int target = smapping[left];
if (target != -1 && --table[1][target] == table[0][target] - 1) {
int length = right - left;
//instead of checking every window, we know exactly the length we want
if ((length / M) == words.length) {
indexes.add(left);
}
++currentFailures;
}
left += M;
}
}
}
return indexes;
}}
__________________________________________________________________________________________________
6ms
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<Integer>();
int wordNum = words.length;
if (wordNum == 0) {
return res;
}
int wordLen = words[0].length();
HashMap<String, Integer> allWords = new HashMap<String, Integer>();
for (String w : words) {
int value = allWords.getOrDefault(w, 0);
allWords.put(w, value + 1);
}
//将所有移动分成 wordLen 类情况
for (int j = 0; j < wordLen; j++) {
HashMap<String, Integer> hasWords = new HashMap<String, Integer>();
int num = 0; //记录当前 HashMap2(这里的 hasWords 变量)中有多少个单词
//每次移动一个单词长度
for (int i = j; i < s.length() - wordNum * wordLen + 1; i = i + wordLen) {
boolean hasRemoved = false; //防止情况三移除后,情况一继续移除
while (num < wordNum) {
String word = s.substring(i + num * wordLen, i + (num + 1) * wordLen);
if (allWords.containsKey(word)) {
int value = hasWords.getOrDefault(word, 0);
hasWords.put(word, value + 1);
//出现情况三,遇到了符合的单词,但是次数超了
if (hasWords.get(word) > allWords.get(word)) {
// hasWords.put(word, value);
hasRemoved = true;
int removeNum = 0;
//一直移除单词,直到次数符合了
while (hasWords.get(word) > allWords.get(word)) {
String firstWord = s.substring(i + removeNum * wordLen, i + (removeNum + 1) * wordLen);
int v = hasWords.get(firstWord);
hasWords.put(firstWord, v - 1);
removeNum++;
}
num = num - removeNum + 1; //加 1 是因为我们把当前单词加入到了 HashMap 2 中
i = i + (removeNum - 1) * wordLen; //这里依旧是考虑到了最外层的 for 循环,看情况二的解释
break;
}
//出现情况二,遇到了不匹配的单词,直接将 i 移动到该单词的后边(但其实这里
//只是移动到了出现问题单词的地方,因为最外层有 for 循环, i 还会移动一个单词
//然后刚好就移动到了单词后边)
} else {
hasWords.clear();
i = i + num * wordLen;
num = 0;
break;
}
num++;
}
if (num == wordNum) {
res.add(i);
}
//出现情况一,子串完全匹配,我们将上一个子串的第一个单词从 HashMap2 中移除
if (num > 0 && !hasRemoved) {
String firstWord = s.substring(i, i + wordLen);
int v = hasWords.get(firstWord);
hasWords.put(firstWord, v - 1);
num = num - 1;
}
}
}
return res;
}
}
__________________________________________________________________________________________________
36188 kb
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> result = new ArrayList<>(s.length());
if (words == null || words.length == 0) {
return result;
}
Map<String, Integer> map = new HashMap<>();
for (String word : words) {
map.put(word, map.getOrDefault(word, 0) + 1);
}
int wordLength = words[0].length();
int numOfWords = words.length;
int totalLength = wordLength * numOfWords;
for (int offset = 0; offset < wordLength; offset++) {
Map<String, Integer> wordToCounter = new HashMap<>(map);
int diff = numOfWords;
for (int toAddIndex = offset; toAddIndex + wordLength <= s.length(); toAddIndex += wordLength) {
String toAdd = s.substring(toAddIndex, toAddIndex + wordLength);
wordToCounter.put(toAdd, wordToCounter.getOrDefault(toAdd, 0) - 1);
if (wordToCounter.get(toAdd) >= 0) {
diff--;
}
if (toAddIndex >= offset + totalLength) {
String toRemove = s.substring(toAddIndex - totalLength, toAddIndex - totalLength + wordLength);
wordToCounter.put(toRemove, wordToCounter.getOrDefault(toRemove, 0) + 1);
if (wordToCounter.get(toRemove) > 0) {
diff++;
}
}
if (diff == 0) {
result.add(toAddIndex + wordLength - totalLength);
}
}
}
return result;
}
}
__________________________________________________________________________________________________
36232 kb
class Solution {
public static List<Integer> findSubstring(String s, String[] words) {
List<Integer> sol = new ArrayList<Integer>();
if (words.length == 0 || words[0].length() == 0)
return sol;
int wordLen = words[0].length(), listLen = words.length, strLen = s.length(), maxIdx = strLen - wordLen * listLen;
if (maxIdx < 0)
return sol;
Map<String, Integer> map = new HashMap<String, Integer>(listLen*4);
for (String ss : words)
map.put(ss, map.getOrDefault(ss, 0) + 1);
char cs[] = s.toCharArray();
for (int i = 0; i < wordLen; i++) {
for (int j = i; j <= maxIdx; j += wordLen) {
String fi = new String(cs,j, wordLen);
if(map.getOrDefault(fi, 0)==0){
continue;
}
Map<String, Integer> temp = new HashMap<String, Integer>(listLen*4);
for (int k = listLen - 1; k >= 0; k--) {
String str = new String(cs,k * wordLen + j, wordLen);
int num = temp.getOrDefault(str, 0) + 1;
if (num > map.getOrDefault(str, 0)) {
j += k * wordLen;
break;
} else if (k == 0)
sol.add(j);
else
temp.put(str, num);
}
}
}
return sol;
}
}
__________________________________________________________________________________________________