【力扣T30】串联所有单词的字串

• 题干
• 数据范围
• 解析
• 总结

---

题干

数据范围

解析

数据范围1e4，复杂度要小于O(n²)
所用算法：哈希表，双指针（滑动窗口）。
哈希表和cnt变量维护了滑动窗口内的信息。两个指针分别是j和j-m*w。把整个s串分段，每段长度为w，枚举匹配起点i，重要的是如何根据tot和wd哈希表的内容判断“有效串”增加还是减少。另外给大家推荐学算法网站acwing。

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        if(words.size()==0) return res;
        int n=s.size(),m=words.size(),w=words[0].size();
        unordered_map<string,int> tot;
        for(auto& word:words) tot[word]++;
        for(int i=0;i<w;i++){
            unordered_map<string,int> wd;
            int cnt=0;
            for(int j=i;j+w<=n;j+=w){
                if(j>=i+w*m){
                    auto word=s.substr(j-m*w,w);
                    wd[word]--;
                    if(wd[word]<tot[word]) cnt--;
                }
                auto word=s.substr(j,w);
                wd[word]++;
                if(wd[word]<=tot[word]) cnt++;
                if(cnt==m) res.push_back(j-(m-1)*w);
            }
        }
        return res;
    }
};

总结

哈希表，双指针，滑动窗口。