优质博文：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;}
}

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