30. 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        Map<String, Integer> targetMap = new HashMap<>();
        for (String word : words) {
            targetMap.put(word, targetMap.getOrDefault(word, 0) + 1);
        }

        List<Integer> answerList = new ArrayList<>();
        int singleWordLength = words[0].length();
        int totalWordLength = singleWordLength * words.length;
        for (int i = 0; i < singleWordLength; i++) {
            // 注意窗口相关状态在 for 循环内侧定义，即对每个起点初始化单独的窗口
            int start = i, matchWordCount = 0;
            Map<String, Integer> windowMap = new HashMap<>();
            for (int j = start; j + singleWordLength - 1 <= s.length() - 1; j += singleWordLength) {
                String word = s.substring(j, j + singleWordLength);

                if (targetMap.containsKey(word)) {
                    // 当前单词可以加入窗口
                    int times = windowMap.getOrDefault(word, 0) + 1;
                    windowMap.put(word, times);
                    if (times == targetMap.get(word)) {
                        matchWordCount++;
                    }

                    while (matchWordCount == targetMap.size()) {
                        // 注意添加逻辑一定要写在 while 里面
                        if (j + singleWordLength == start + totalWordLength) {
                            answerList.add(start);
                        }

                        String leftmostWord = s.substring(start, start + singleWordLength);
                        int leftmostWordTimes = windowMap.get(leftmostWord);
                        if (leftmostWordTimes == targetMap.getOrDefault(leftmostWord, Integer.MAX_VALUE)) {
                            matchWordCount--;
                        }
                        windowMap.put(leftmostWord, leftmostWordTimes - 1);
                        start += singleWordLength;
                    }
                } else {
                    // 当前单词无法加入窗口，清空窗口相关状态
                    windowMap.clear();
                    start = j + singleWordLength;
                    matchWordCount = 0;
                }
            }
        }

        return answerList;
    }
}

题意表明所有单词的长度相同，所以我们可以多起点遍历，每次遍历步长为单个单词的长度，效率更高。

References

30. Substring with Concatenation of All Words