76.串联所有单词的子串

题目

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/substring-with-concatenation-of-all-words

解题思路

因为words里面的word的长度都是一样的，考虑用滑动窗口。

先用哈希表存储words各个单词的出现次数从左往右遍历一遍s字符串，窗口大小固定，查看当前窗口的字符字串是否符合条件即可。代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string,int> search;
        vector<int> res;
        for(auto&w:words) ++search[w];
        int n=s.size();
        int num=words.size();
        int len=words[0].size();
        
        for(int i=0;i<n-num*len+1;i++){
            unordered_map<string,int> sub;
            //match
            int j=0;
            for(;j<num;j++){
                string tmp=s.substr(i+j*len,len);
                if(!search.count(tmp))break;
                if(++sub[tmp]>search[tmp])break;
            }
            if(j==num)res.push_back(i);
        }
        return res;
    }
};