30-串联所有单词的子串——hard

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words

思路：

• 维护单词长度个滑动窗口，每个单词长度相同，所以每次滑动固定长度。
• 如果当前单词不在words中，说明这个窗口内的内容无法继续匹配了，重置计数器和左指针。
• 在其中时需要考虑如果该单词个数大于words中个数时，需要移动左指针，以及将最左侧单词计数减一。
• 考虑一些边界条件，例如s长度比words中单词长度短，s或words为空。

复杂度分析：
时间复杂度O(n)
空间复杂度O(n)

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
    if(words.length===0 || s.length === 0) return [];
    const Counter = (array)=>{
        let map = new Map();
        for(let i = 0;array && i < array.length; i++){
            let tmp = map.get(array[i]);
            if(tmp !== undefined){
                map.set(array[i],tmp+1);
            }else{
                map.set(array[i],1);
            }
        }
        return map;
    }
    let word_num = words.length;
    let one_word = words[0].length;
    let n = s.length;
    if(n < one_word) return [];
    let ans = [];
    words = Counter(words);
    for(let i = 0;i < one_word ;i++){
        let left = i;
        let right = i;
        let cur_map = Counter();
        let cnt = 0;
        while(right + one_word <= n){
            let w = s.slice(right,right+one_word);
            right += one_word;
            if(words.get(w)){
                cnt += 1;
                if(cur_map.get(w)){
                    cur_map.set(w,cur_map.get(w)+1);
                }else{
                    cur_map.set(w,1);
                }
                while(cur_map.get(w) > words.get(w)){
                    let left_w = s.slice(left,left+one_word);
                    left += one_word;
                    if(cur_map.get(left_w)){
                        cur_map.set(left_w,cur_map.get(left_w)-1);
                    }else{
                        cur_map.set(left_w,0);
                    }
                    cnt -=1;
                }
                if(cnt === word_num) ans.push(left)
            }else{
                cnt = 0;
                left = right;
                cur_map.clear();
            }
        }
    }
    return ans;
};