[Link] https://leetcode.com/problems/substring-with-concatenation-of-all-words/
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
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
int wlen = words[0].length(), slen = s.length(), wn = words.length, cnt, keyNum = 0;
HashMap<String, Integer> hm = new HashMap<>();
HashMap<String, Integer> cntMap = new HashMap<>();
LinkedList<Integer> answer = new LinkedList<>();
for(String word : words) {
if(hm.containsKey(word)) hm.put(word, hm.get(word) + 1);
else {
keyNum++;
hm.put(word, 1);
}
}
for(int i = 0, upper = slen - wlen*wn; i <= upper; i++) {
cntMap.clear();
cnt = 0;
for(int j = 0; j < wn; j++) {
String cur = s.substring(i + j * wlen, i + (j + 1) * wlen);
if(hm.containsKey(cur)) {
Integer oldVal = cntMap.put(cur, cntMap.getOrDefault(cur, 0) + 1);
if(oldVal == null) oldVal = 0;
if(oldVal == hm.get(cur) - 1) cnt++;
else if(oldVal == hm.get(cur)) break;
} else break;
}
if(cnt == keyNum) answer.add(i);
}
return answer;
}
}