题目描述

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

算法1

(双指针) $O(len(s) * len(word))$

见代码注释，和参考文献视频。

时间复杂度

一共做了$O(len(word))$次双指针扫描，
每次扫描两个指针均最多移动$len(s) / len(word)$次，
每次移动做$O(1)$次hash查询，
每次hash查询的复杂度是$O(len(word))$，
所以总时间复杂度是$O(len(s) * len(word))$

参考文献

https://www.bilibili.com/video/BV1Lb411w7L5?t=187&p=2

C++ 代码

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        // corner case
        if (s.empty() || words.empty()) return {};

        // 初始化，记录需要哪些单词，各需要几个
        unordered_map<string, int> word2cnt;
        for (string &word: words) ++word2cnt[word]; 
        vector<int> res;
        int n = s.size(), m = words.size(), w = words[0].size();

        // 将每个单词看作一个整体，分别以0, 1, .., w - 1为开头，w为间隔，做双指针扫描
        for (int i = 0; i < w; ++i){
            int need = m;
            unordered_map<string, int> hash;
            int l = i, r = i + w;
            while (r <= n){
                string cur_word = s.substr(r - w, w);
                // 如果碰到不需要的单词，跳过它，从它的后面重新开始双指针扫描，这一处剪枝非常重要，可以快10倍
                if (!word2cnt.count(cur_word)){
                    need = m;
                    l = r; r = l + w;
                    hash.clear();
                    continue;
                }
                // 如果是需要的单词，更新计数器
                ++hash[cur_word];
                // 如果没有超额
                if (hash[cur_word] <= word2cnt[cur_word]) --need;
                // 如果超额了，调整左指针至不超额
                else{
                    while (hash[cur_word] > word2cnt[cur_word]){
                        string head_w = s.substr(l, w);
                        l += w;
                        if (hash[head_w]-- <= word2cnt[head_w]) ++need;
                    }
                }
                if (need == 0) res.push_back(r - m * w);
                r += w;
            }    
        }
        return res;
    }
};