Leetcode刷题：串联所有单词的子串-一一网

这是我参与新手入门的第3篇文章。

一、题目描述

给定一个字符串 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"]
输出：[]
复制代码

示例3：

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
复制代码

提示：

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

二、思路

一、从s入手，判断s每个子串是否可以由words的单词组合而成，符合的把下标保存起来，最后返回即可

判断字串是否符合要求：

维护两个HashMap
把所有的单词words存到一个哈希表wordsMap里，key存单词，value 存单词出现的个数（因为给出的单词可能会有重复）
for循环判断s的每个子串，扫描每个子串tmpS的单词是否匹配words的单词

二、优化前面的方法从而降低时间复杂度

前面的解法s中每次只移动1个字符；优化之后改成每次移动一个单词的长度，此时s子串的所有可能结果有3种，所以外层循环小于一个单词的长度即可

i从0开始，每次移动一个单词的长度
i从1开始，每次移动一个单词的长度
i从2开始，每次移动一个单词的长度
右窗口每次移动一个单词的长度，获取该单词word；

如果该单词不在wordsMap中，说明该单词可以直接跳过，缩小窗口，左指针移动到右指针的位置；

如果该单词在wordsMap中，如果该单词在子串中的个数，比在wordsMap中的个数还多，说明需要缩小窗口，即左指针向右移动，一直到该单词在子串中的个数不比wordsMap中多为止

在求解过程中首先想到通过递归求出全排列单词组合的方法求出所有的字符串然后去比较，但该方法耗时过长时间复杂度太高。于是转化思路模拟了一个最大长度为给定单词长度之和的滑块（words.length * len），让滑块在字符串S上滑动，通过判定滑块捏的字符是否匹配给定单词来存储下标。

三、AC代码

方式一、

var findSubstring = function(s, words) {
    if (!s || !words || !words.length) {
        return [];
    }

    // key是单词，value是出现的次数
    let wordsMap = new Map();
    for (let word of words) {
        wordsMap.set(word, (wordsMap.get(word) || 0)+ 1);  
    }

    // 一个单词的长度
    let oneWordsLen = words[0].length;
    // 所有单词的长度
    let allWordsLen = oneWordsLen * words.length;

    let result = [];
    // 开始扫描s的每个子串，s每次只移动一位
    for (let i = 0; i < s.length - allWordsLen + 1; i++) {
        // s的一个子串
        let tmpS = s.substring(i, i + allWordsLen);

        // 存放子串各个单词及其出现次数，最后用于和wordsMap做比较
        let map = new Map();

        // 判断s的子串是否可以拆成words里所有单词
        let tmpLength = 0;
        for (let j = 0; j < allWordsLen; j += oneWordsLen) {
            let curWord = tmpS.substring(j, j + oneWordsLen);
            map.set(curWord, (map.get(curWord) || 0) + 1);
            // words不包含该单词，直接跳过，判断下一个单词
            if (!wordsMap.has(curWord)) {
                break;
            }
            // 当前单词的数量比words中该单词的数量还多，也跳过判断下一个单词
            if (map.get(curWord) > wordsMap.get(curWord)) {
                break;
            }
            tmpLength += oneWordsLen;
        }
        // 长度相等，说明该字串可以拆成words里的所有单词
        if (tmpLength === tmpS.length) {
            result.push(i);
        }
    }

    // 返回能拆分成words的所有起始索引
    return result;
};
复制代码

方式二、

var findSubstring = function(s, words) {
    if (!s || !words || !words.length) {
        return [];
    }

    // key是单词，value是出现的次数
    let wordsMap = new Map();
    for (let word of words) {
        wordsMap.set(word, (wordsMap.get(word) || 0)+ 1);  
    }

    // 一个单词的长度
    let oneWordsLen = words[0].length;
    // 所有单词的长度
    let allWordsLen = oneWordsLen * words.length;
    if (s.length < allWordsLen) {
        return [];
    }

    let res = [];
    // 为什么要小于一个单词的长度，即i < oneWordsLen ？
    // 因为每次移动一个单词的长度，即3个字符，所以所有的移动被分成了三类 1、从0开始，每次移动一个单词的长度；2、从1开始，每次移动一个单词的长度；3、从2开始，每次移动一个单词的长度
    // 每次窗口大小 wordsLen，每次后移一个单词长度，由左右窗口维持当前窗口位置
    for (let i = 0; i < oneWordsLen; i++) {
        let left = i;
        let right = i;

        // 符合要求的单词数
        let count = 0;
        // 符合要求的word窗口
        let tmpMap = new Map();

        // 右窗口不超出s的长度，每次移动一个单词的长度
        while (right + oneWordsLen <= s.length) {
            const word = s.substring(right, right + oneWordsLen);
            right += oneWordsLen; // 右窗口右移

            // words中没有这个单词，则左指针移动，缩小窗口，直接右移到这个单词后面
            if (!wordsMap.has(word)) {
                // 左指针直接移动到右窗口的位置，包含该不符合字符的串都直接跳过
                left = right;
                // 窗口内单词统计map清空，重新统计
                tmpMap.clear();
                // 符合要求的单词数清0
                count = 0;
            } else { 
                // 统计当前子串中这个单词出现的次数
                tmpMap.set(word, (tmpMap.get(word) || 0) + 1);
                count++;
                // 一直减，减到不大于，即重复单词前面的都是没用的，左窗口直接跳过
                while (tmpMap.get(word) > wordsMap.get(word)) {
                    let tmpWord = s.substring(left, left + oneWordsLen);
                    count--;
                    tmpMap.set(tmpWord, (tmpMap.get(tmpWord) || 0) - 1);
                    // 左窗口右移动，即缩小
                    left += oneWordsLen;
                }
                // 当前窗口字符串个数满足要求，此时窗口的单词刚好满足words
                if (count == words.length) {
                    res.push(left);
                }
            }             
        }
    }

    // 返回能拆分成words的所有起始索引
    return res;
};
复制代码