2022秋招备战！每天写至少一篇Leetcode里Hard难度题目的题解

30. 串联所有单词的子串

给定一个字符串 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] 由小写英文字母组成

滑动窗口

本题虽然核心思想是滑动窗口，也很好想到，但是里面的2个细节优化还是挺没有规律的。一个可以利用的重要是所有的单词长度都相等，同时存在以下2个优化。

1. 如果当前窗口内单词出现非法单词，我们直接break。
2. 如果当前窗口内某个单词的数量大于给定的单词的数量，我们直接break。

如何判断窗口内是合法的，对此我们用2个哈希表来判断。

一个哈希表作为字典。在滑动窗口开始前就初始化好。

另外一个哈希表代表我们窗口内的单词数量和种类。

易实现以下2种不合法情况

1. if (dic.find(cur) == dic.end()) break; 如果当前单词不在我们的字典内，可以直接break
2. if (window[cur] > dic[cur]) break;如果当前单词的数量超标，也可以直接break

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        int n = s.size(), m = words.size(), len = words[0].size();
        unordered_map<string, int> dic;
        for (auto& word : words) dic[word]++;
        unordered_map<string, int> window;
        for (int i = 0, j = 0; i + len * m <= n; i++) {
            for (j = i; j < i + len * m; j += len) {
                string cur = s.substr(j, len);
                if (dic.find(cur) == dic.end()) break;           
                window[cur]++;
                if (window[cur] > dic[cur]) break;        
            }
            if (j == i + len * m) res.push_back(i);
            window.clear();
        }
        return res;

    }
};