leetcode

0 static auto _ = []() {

1 ios_base::sync_with_stdio(false);

2 cin.tie(NULL);

3 cout.tie(NULL);

4 return 0;

5 };

6

7 class Solution {

8 static bool check(const unordered_map<string, int> &count, const string &s, int len) {

9 static unordered_map<string, int> lcount;

10 lcount.clear();

11 for (int i = 0; i < s.size(); i += len) {

12 string word = s.substr(i, len);

13 const auto it = count.find(word);

14 if (it == count.end()) return false;

15 if (++lcount[word] > it->second) return false;

16 }

17 return true;

18 }

19

20 public:

21 vector<int> findSubstring(const string &s, const vector<string> &words) const {

22 const int n = words.size(), m = words[0].size();

23 unordered_map<string, int> count;

24 for (const string &word : words)

25 count[word]++;

26

27 vector<int> res;

28 for (int i = 0; i + m * n <= s.size(); i++) {

29 if (check(count, s.substr(i, m * n), m)) {

30 res.push_back(i);

31 }

32 }

33 return res;

34 }

35 };