[2022-06-23]30. 串联所有单词的子串👋哈希表👋字符串👋滑动窗口

[webVueBlog]

题目链接: https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words

难度: Hard
标签: 哈希表 字符串 滑动窗口

[dreamjean]

30. 串联所有单词的子串

Description

Difficulty: 困难

Related Topics: 哈希表, 字符串, 滑动窗口

给定一个字符串 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 <= 10⁴
• s 由小写英文字母组成
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] 由小写英文字母组成

Solution

思路：

• 使用两个哈希表，分别记录words的单词和滑动窗口内的单词
• 滑动窗口每次滑动一个单词的距离

Language: JavaScript

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
    const [wordsCount, size] = [words.length, words[0].length];  
    const limit = s.length - wordsCount * size;  // 遍历的时候直接先扣除words的总长度
    const map = {};
    const ans = [];

    words.forEach(word => map[word] ? map[word]++ : map[word] = 1);   // 对words中的单词进行记数

    for (let i = 0; i <= limit; i++) {
        if (!map[s.slice(i, i + size)]) continue;  // 每次滑动一个单词的距离，如果map中没有这个单词的数据，直接跳过

        const seen = {};  
        let [j, count] = [i, 0];   // 从 i 的位置开始扩大窗口， count用于记录窗口内单词的数量
        while (count < wordsCount) {  
            const sub = s.slice(j, j + size);    
            seen[sub] ? seen[sub]++ : seen[sub] = 1;   // 记录窗口内每个单词的数量
            if (!map[sub] || seen[sub] > map[sub]) break;  // map中不存在这个单词或者窗口内这个单词的数量大于map中的数量的时候直接中断退出

            j += size;  // 每次移动一个单词的距离
            count++;  
        }

        if (count === wordsCount) ans.push(i); 
    }

    return ans;
};