美团二面算法 之 串联所有单词的子串[困难]

优质博文：IT-BLOG-CN

一、题目

给定一个字符串s和一个字符串数组words。words中所有字符串长度相同。s中的串联子串是指一个包含words中所有字符串以任意顺序排列连接起来的子串。

例如，如果words = ["ab","cd","ef"]， 那么abcdef，abefcd，cdabef，cdefab，efabcd，和efcdab都是串联子串。acdbef不是串联子串，因为他不是任何words排列的连接。

返回所有串联子串在s中的开始索引。你可以以任意顺序返回答案。

示例 1：
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为words.length == 2同时words[i].length == 3，连接的子字符串的长度必须为6。子串barfoo开始位置是0。它是words中以["bar","foo"]顺序排列的连接。子串foobar开始位置是9。它是words中以["foo","bar"]顺序排列的连接。输出顺序无关紧要。返回[9,0]也是可以的。

示例 2：
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为words.length == 4并且words[i].length == 4，所以串联子串的长度必须为16。s中没有子串长度为16并且等于words的任何顺序排列的连接。所以我们返回一个空数组。

示例 3：
输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为words.length == 3并且words[i].length == 3，所以串联子串的长度必须为9。
子串foobarthe开始位置是6。它是words中以["foo","bar","the"]顺序排列的连接。
子串barthefoo开始位置是9。它是words中以["bar","the","foo"]顺序排列的连接。
子串thefoobar开始位置是12。它是words中以["the","foo","bar"]顺序排列的连接。

::: warning
1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i]和s由小写英文字母组成
:::

二、代码

思路： 记words的长度为m，words中每个单词的长度为n，s的长度为ls。首先需要将s划分为单词组，每个单词的大小均为n（首尾除外）。这样的划分方法有n种，即先删去前i（i=0∼n−1）个字母后，将剩下的字母进行划分，如果末尾有不到n个字母也删去。对这n种划分得到的单词数组分别使用滑动窗口对words进行类似于「字母异位词」的搜寻。

划分成单词组后，一个窗口包含s中前m个单词，用一个哈希表differ表示窗口中单词频次和words中单词频次之差。初始化differ时，出现在窗口中的单词，每出现一次，相应的值增加1，出现在words中的单词，每出现一次，相应的值减少1。然后将窗口右移，右侧会加入一个单词，左侧会移出一个单词，并对differ做相应的更新。窗口移动时，若出现differ中值不为0的键的数量为0，则表示这个窗口中的单词频次和words中单词频次相同，窗口的左端点是一个待求的起始位置。划分的方法有n种，做n次滑动窗口后，即可找到所有的起始位置。

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        // 1、先确定s串的首字母是words中的某个单子的首字母，所以要遍历一个 word 长度的循环；
        // 2、将s串，按照 words 的长度，拆分成一组单词，存放值 Map 中；
        // 3、根据 words 中的单词，对 Map中的数据进行 -1；
        // 4、开始移动s串中的单子，不符合时 右边添加一个单词，左边移除一个单词，如果 Map为空时，说明是符合要求，将下表添加至列表中
        List<Integer> res = new ArrayList<Integer>();
        if (words.length == 0) {
            return res;
        }
        int m = words.length, n = words[0].length(), ls = s.length();

        for (int i = 0; i < n; i++) {
            // 如果单子的长度已经超出了ls的长度，就可以直接返回了
            if (i + m * n > ls) {
                return res;
            }

            Map<String, Integer> differ = new HashMap<String, Integer>();
            for (int j = 0; j < words.length; j++) {
                // 需要 i 的参与
                String word = s.substring(i + j * n, i + (j + 1) * n);
                differ.put(word, differ.getOrDefault(word, 0) + 1);
            }

            for (String word: words) {
                differ.put(word, differ.getOrDefault(word, 0) - 1);
                if (differ.getOrDefault(word, 0) == 0) {
                    differ.remove(word);
                }
            }

            // 滑动 s 串 难点【每次滑动一个单词】
            for (int start = i; start < ls - m * n + 1; start += n) {
                // 开始移动，先删除掉最左边的单词
                if (start != i) {
                    String word = s.substring(start - n , start);
                    differ.put(word, differ.getOrDefault(word, 0) - 1);
                    if (differ.getOrDefault(word, 0) == 0) {
                        differ.remove(word);
                    }

                    // 添加右边元素，我们需要 - n 而不是1，因为是以word为单位的
                    word = s.substring(start + (m-1) * n, start + m * n);
                    differ.put(word, differ.getOrDefault(word, 0) + 1);

                    if (differ.getOrDefault(word, 0) == 0) {
                        differ.remove(word);
                    }
                }

                // 判断如果满足条件，将start存入返回值中
                if (differ.isEmpty()) {
                    res.add(start);
                }
            }
        }
        return res;
    }
}
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

时间复杂度： O(ls×n)其中ls是输入s的长度，n是words中每个单词的长度。需要做n次滑动窗口，每次需要遍历一次s。
空间复杂度： O(m×n)其中m是words的单词数，n是words中每个单词的长度。每次滑动窗口时，需要用一个哈希表保存单词频次。