js实现串联所有单词的子串-一一网

这是我参与更文挑战的第6天，活动详情查看：更文挑战

题目

描述

给定一个字符串 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的单词
- 如果当前扫描的单词curWord存在哈希表wordsMap中，把该单词存到新的哈希表map中；不存在则跳过
- 然后判断新的map中该单词的value是否大于之前的wordsMap该单词的value；如果大于，说明该子串不是要找的，跳过接着判断下一个子串即可；如果不大于，说明该curWord符合words的单词，计算一下子串符合words的长度，接着判断下一个单词的情况
- 子串扫描结束，如果子串的全部单词都符合（此处用长度作为标记，长度相等即该子串是符合words里所有拆分的单词），保存下开始下标
返回所有开始下标结果即可

代码

/**
 * 
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
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;
};


作者：xing-guang-29
链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/solution/30-chuan-lian-suo-you-dan-ci-de-zi-chuan-fnp9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复制代码