利用分组遍历精简字符串的匹配。

30.题目链接-来源：力扣（LeetCode）

给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

示例 1：

输入：s = “barfoothefoobarman”, words = [“foo”,”bar”]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 “barfoo” 和 “foobar” 。
输出的顺序不重要, [9,0] 也是有效答案。

思路：

本题可以先从暴力解着手开展思路。记 words 的单词个数为 wNum， 每个单词长度为 wLen。我们可以遍历 s 中的每一位，以之为起点开始向后查找单词，总共查找 wNum 次，每次跨越 wLen 个字符，用一个哈希表统计单词出现次数，并与 words 中的次数进行比较，若一致则可将此位加入结果列表中。
我们如何优化暴力解呢？考虑如下字符串实例 s = “wordgoodgoodgoodcestword”，words = [“word”,”good”,”best”,”word”]，我们以 偏移量0 为起点 得到字符串 s0 “wordgoodgoodgood”，进行统计，我们得到了 3 个 “good”，现在我们需要寻找下一个作为起点的偏移量。

  • 我们的统计是以单词为单位的，对于 s0，我们希望其统计信息可以复用，那么 s1、s2、s3 由于字符的错位，是无法复用统计信息的。而对于 s4，我们可以简单地在统计信息中剔除头部的 1个 “word”，加上尾部的 1个 “best”，而不需要重新遍历中间的字符。于是我们可以将子串按照起点坐标对 wLen 的余数进行分组，这样分成了 wLen 组，同一组内的统计信息可以从前往后依次复用。
  • 对于其中某一组，比如余数为 0 的组，子串 s4、s8 当中必然包含了超过 1 个的 “good”，因此这部分子串我们可以直接跳过，直接跳转到 s12 继续我们的匹配。
  • 对于具体的某一串，我们有时不需要遍历整个串就能判断该串不符合条件。比如 s0，当我们统计到第 2 个 “good” 出现的时候，单词数量已经超标，即可判断该串不符合要求，跳转到 s12 继续匹配。同理，对于 s12，我们统计到 “cest” 时发现单词表中并没有这个单词，我们也能直接跳过，转到 s20 继续匹配。
    具体实现中，为了在常数时间内判断出当前子串是否符合条件，我们可以先预处理一个哈希表 example，存储 words 中每个单词的个数。在子串收集单词的时候，我们用一个计数 collectedNum 来统计已经收集到的单词，同时建立一个临时哈希表 count 统计当前子串每个单词的个数信息，如果单词已存在于 example 中且个数没有超标，我们就将其计入 count 中，同时 collectedNum 步进。否则，我们认为该单词非法（可能是个数超标，也可能是单词根本不存在），我们再分别作相应的处理。
    时间复杂度：O(n)
    空间复杂度：O(m) m 为 words 的单词个数 wNum

实现：

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
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int wLen = words[0].length(), wNum = words.length, sLen = s.length();
        List<Integer> ret = new LinkedList<>();
        
        Map<String, Integer> example = new HashMap<>() {{
            for (String eachWord : words) {
                put(eachWord, getOrDefault(eachWord, 0) + 1);
            }
        }};
        
        int headBound = sLen - wLen * wNum;
        for (int i = 0; i < wLen; i++) {
            Map<String, Integer> count = new HashMap<>();
            
            int collectedNum = 0;
            for (int head = i, j = head; head <= headBound;) {
                while (collectedNum < wNum && j + wLen <= sLen) {
                    String toCollect = s.substring(j, j + wLen);
                    if (example.containsKey(toCollect)) {
                        count.put(toCollect, count.getOrDefault(toCollect, 0) + 1);
                        collectedNum++;
                        
                        int countBound = example.get(toCollect);
                        while (count.get(toCollect) > countBound) {// 当有多余重复的串出现时，删除至数量符合要求为止
                            String toDelete = s.substring(head, head + wLen);
                            head += wLen;
                            collectedNum--;
                            int value = count.get(toDelete);
                            if (value <= 1) {
                                count.remove(toDelete);
                            } else {
                                count.put(toDelete, value - 1);
                            }    
                        }
                    } else {
                        head = j + wLen;
                        count.clear();
                        collectedNum = 0;
                    }
                    j += wLen;
                }
                if (collectedNum == wNum) {
                    ret.add(head);
                }
                
                if (head <= headBound) {
                    String toDelete = s.substring(head, head + wLen);
                    int value = count.get(toDelete);
                    if (value <= 1) {
                        count.remove(toDelete);
                    } else {
                        count.put(toDelete, value - 1);
                    }
                    head += wLen;
                    collectedNum--;
                }
            }
        }
        return ret;
    }
}