串联所有单词的子串
给定一个字符串 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"] 顺序排列的连接。
提示：
- 1 <= s.length <= 104
- 1 <= words.length <= 5000
- 1 <= words[i].length <= 30
- words[i] 和 s 由小写英文字母组成
解法：滑动指针
这题属于困难题型，可以使用滑动窗口进行解决。
首先是当前窗口内的内容是否满足条件的判断，我们可以先用一个hashmap提前计算好每个单词所需要出现的频次。滑动窗口时，我们以一个单词的距离进行滑动，这样就可以判断新进入窗口的单词和出窗口单词对diffmap的影响，如果出窗口单词是我们要的，那么该单词对应的所需数量就+1，进窗口的单词对应所需数量就-1。最终，只要所有的单词所需数量为0，那么就说明该窗口内的内容满足条件。
由于我们是按照wordwidth的长度进行滑动，所以相对于按照wordwidth的长度把s进行了划分。如下：
s = barfoothefoobarman，单词长度是3，划分结果就是：
bar|foot|the|foot|bar|man
那么我们只需要进行偏移划分就可以得到所有的组合，也就是说offset<wordwidth即可
当下标从 i=0 开始时，划分的结果是：bar | foo | the | foo | bar | man
当下标从 i=1 开始时，划分的结果是：arf | oot | hef | oob | arm | an
当下标从 i=2 开始时，划分的结果是：rfo | oth | efo | oba | rma | n
当下标从 i=3 开始时，划分的结果是：foo | the | foo | bar | man
此外题目中的对于当前窗口是否满足条件的判断，可以进一步简化。可以用diffCount来记录还有几个词汇不满足条件，如果diffCount == 0那么就满足条件。这样可以把判断的时间复杂度从O(不同单词数)->O(1)
function findSubstring(s: string, words: string[]): number[] {
const n = s.length
const m = words.length
const wordWidth = words[0].length
const windowWidth = m * wordWidth // 窗口大小
const res: number[] = []
// 不需要遍历整个s, s按照单词长度进行划分，所以周期就是单词长度，所以 offset < wordWidth 即可.
// 比如m=3的时候，offset=0和offset=3的划分结果是一样的。
let offset = 0 // 偏移量。
while(offset < wordWidth){
// 初始化窗口内的词频目标，当所有词频都-到0时，说明符合条件
const diffMap = new Map<string, number>()
let i = 0
while(i < m){
if(!diffMap.has(words[i])) diffMap.set(words[i], 1) // 还没记录过的单词
else{
diffMap.set(words[i], diffMap.get(words[i]) + 1) // 已记录过的增加频次
}
i++
}
let start = offset
// 先计算当前窗口内的词频
for(let i = offset; i < windowWidth + offset; i = i + wordWidth){
const curWord = s.slice(i, i + wordWidth)
if(diffMap.has(curWord)){
diffMap.set(curWord, diffMap.get(curWord) - 1) // 该目标 - 1
}
}
// 滑动当前窗口
while(start + windowWidth <= n){
// 检查当前窗口是否满足条件
let isMatch = true;
// 遍历 diffMap，检查所有单词频次是否为 0
for (const [word, count] of diffMap.entries()) {
if (count !== 0) {
isMatch = false;
break; // 只要有一个词频不为0，直接判定不匹配
}
}
// 若匹配，记录窗口起始索引（start 是初始窗口起始位置）
if (isMatch) {
res.push(start);
}
// 滑动窗口
const nextInWord = s.slice(start + windowWidth, start + windowWidth + wordWidth) // 下一个要检查的单词
const nextOutWord = s.slice(start, start + wordWidth) // 下一个要出窗口的单词
if(diffMap.has(nextInWord)){
// 检查单词存在
diffMap.set(nextInWord, diffMap.get(nextInWord) - 1) // 该单词里目标 - 1
}
if(diffMap.has(nextOutWord)){
diffMap.set(nextOutWord, diffMap.get(nextOutWord) + 1) // 该单词离目标 + 1
}
start += wordWidth // 按照单词长度进行滑动
}
offset++
}
return res
};