leetcode-30. 串联所有单词的子串

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

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

解法
n表示字符串s的长度；
m表示words数组中单词的数量；
w表示words数组中每个单词的长度，words中每个单词的长度相等，均为words[0]；

分组的思想：因为words中的每个单词长度相同，所以将字符串根据单词长度w分为 $n/w$ 个块。

双指针：第一个指针i遍历[0,w-1]，对于每个i，指针j每次j+=w向后遍历。

使用2个哈希表，map1 存 words 中的单词的 str–>int 数量，map2 是一个滑动窗口，其中最多只能存 m 个长度为 w 的单词。

cnt记录 map2 中有多少个单词是map1中的。

map1使用words数组初始化，比较好理解。
map2有 2 个操作，分别是添加单词 word 和删除单词 word：

1. 窗口满了才删除单词，窗口由[i,j]维护，有m个单词表示窗口满了。将窗口最前面的单词删除，删除后，判断该单词是否是words中的单词，是就把cnt–。
2. j=0时，就可以像 map2 中添加 word 了，添加的 word 是 s[j, j+w]，添加单词 word 后，也要判断该单词是否是 words 中的单词，是就把cnt++。

最后，在 map2 中找到 m 个单词在 map1 中时（即cnt==m），意味着找到了 words 数组中所有单词，就保存 从 j 向前推 m-1 个单词 的起始位置。

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        if (words.empty()) return res;

        int n = s.size(), m = words.size(), w = words[0].size();

        unordered_map<string, int> map1;
        for (auto word : words) map1[word]++;

        for (int i = 0; i < w; i++)
        {
            unordered_map<string, int> map2;
            int cnt = 0; // 记录 map2 中有多少个单词是map1中的
            for (int j = i; j + w <= n; j+=w)
            {
                // 窗口满了，达到了m*w的长度开始删元素
                if (j - i >= m * w) // [i,j]达到了 words数组中的总单词长度
                {
                    // 将窗口中前面的word删除
                    auto word = s.substr(j - m * w, w);
                    map2[word]--;// 删除
                    if (map2[word] < map1[word]) cnt --;
                }
                
                // [i,j]之间的单词大小 < words的单词总长 m * w
                auto word = s.substr(j, w);
                map2[word]++;
                if (map2[word] <= map1[word]) // 判断 word 是否是map1中的，即是否是words数组中的单词
                    cnt ++; // 是map1中的单词，就把cnt++，说明找到1个单词
                
                // 找到m个单词的时候，即找到words数组中所有单词，就保存字串的起始位置
                if (cnt == m) res.push_back(j - (m-1)*w); // j和起始位置之间 差了 m-1个单词的距离
            }
        }
        return res;
    }
};

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/substring-with-concatenation-of-all-words
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。