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
| public static List<Integer> solution2(String s, String[] words) {
List<Integer> res = new ArrayList<>();
Map<String, Integer> wordsMap = new HashMap<>();
if (s.length() == 0 || words.length == 0) return res;
for (String word: words) {
// 主串s中没有这个单词，直接返回空
if (s.indexOf(word) < 0) return res;
// map中保存每个单词，和它出现的次数
wordsMap.put(word, wordsMap.getOrDefault(word, 0) + 1);
}
// 每个单词的长度， 总长度
int oneLen = words[0].length(), wordsLen = oneLen * words.length;
// 主串s长度小于单词总和，返回空
if (wordsLen > s.length()) return res;
// 只讨论从0，1，...， oneLen-1 开始的子串情况，
// 每次进行匹配的窗口大小为 wordsLen，每次后移一个单词长度，由左右窗口维持当前窗口位置
for (int i = 0; i < oneLen; ++i) {
// 左右窗口
int left = i, right = i, count = 0;
// 统计每个符合要求的word
Map<String, Integer> subMap = new HashMap<>();
// 右窗口不能超出主串长度
while (right + oneLen <= s.length()) {
// 得到一个单词
String word = s.substring(right, right + oneLen);
// 有窗口右移
right += oneLen;
// words[]中没有这个单词，那么当前窗口肯定匹配失败，直接右移到这个单词后面
if (!wordsMap.containsKey(word)) {
left = right;
// 窗口内单词统计map清空，重新统计
subMap.clear();
// 符合要求的单词数清0
count = 0;
} else {
// 统计当前子串中这个单词出现的次数
subMap.put(word, subMap.getOrDefault(word, 0) + 1);
++count;
// 如果这个单词出现的次数大于words[]中它对应的次数，又由于每次匹配和words长度相等的子串
// 如 ["foo","bar","foo","the"] "| foobarfoobar| foothe"
// 第二个bar虽然是words[]中的单词，但是次数超了，那么右移一个单词长度后 "|barfoobarfoo|the"
// bar还是不符合，所以直接从这个不符合的bar之后开始匹配，也就是将这个不符合的bar和它之前的单词(串)全移出去
while (subMap.getOrDefault(word, 0) > wordsMap.getOrDefault(word, 0)) {
// 从当前窗口字符统计map中删除从左窗口开始到数量超限的所有单词(次数减一)
String w = s.substring(left, left + oneLen);
subMap.put(w, subMap.getOrDefault(w, 0) - 1);
// 符合的单词数减一
// 左窗口位置右移
left += oneLen;
}
// 当前窗口字符串满足要求
if (count == words.length) res.add(left);
}
}
}
return res;
}
|
