leetcode30 串联所有单词的子串

思路：

滑动窗口+哈希表。

实现：

 1 class Solution {
 2 public:
 3     set<string>check(map<string,int>&cur,map<string,int>&mp){
 4         set<string>st;
 5         for(auto it:mp){
 6             string key=it.first;
 7             int val=it.second;
 8             if(!cur.count(key) or cur[key]!=val){
 9                 st.insert(key);
10             }
11         }
12         return st;
13     }
14     vector<int> findSubstring(string s, vector<string>& w) {
15         int n=s.length(),m=w.size(),l=w[0].length();
16         vector<int>res;
17         map<string,int>mp;
18         for(auto it:w){
19             mp[it]++;
20         }
21         for(int i=0;i){
22             map<string,int>cur;
23             int cnt=0;
24             int j=i;
25             for(;j+l-1l){
26                 string tmp=s.substr(j,l);
27                 cur[tmp]++;
28                 cnt++;
29             }
30             if(cnt<m){
31                 break;
32             }
33             set<string>diff=check(cur,mp);
34             if(diff.empty()){
35                res.push_back(j-l*m);
36             }
37             for(;j+l-1l){
38                 string tmp=s.substr(j,l);
39                 string last=s.substr(j-m*l,l);
40                 cur[tmp]++;
41                 cur[last]--;
42                 if(cur[last]==0){
43                     cur.erase(last);
44                 }
45                 if(!mp.count(tmp) or cur[tmp]!=mp[tmp]){
46                     diff.insert(tmp);
47                 }
48                 else{
49                     diff.erase(tmp);
50                 }
51                 if(cur.count(last)){
52 
53                     if(!mp.count(last) or cur[last]!=mp[last]){
54                         diff.insert(last);
55                     }
56                     else{
57                         diff.erase(last);
58                     }
59                 }
60                 else{
61                     if(mp.count(last)){
62                         diff.insert(last);
63                     }
64                     else{
65                         diff.erase(last);
66                     }
67                 }
68                 if(diff.empty()){
69                     res.push_back(j-l*(m-1));
70                 }
71             }
72         }
73         return res; 
74     }
75 };