leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0030.cpp (1069B)

      1 static auto _ = []() {
      2     ios_base::sync_with_stdio(false);
      3     cin.tie(NULL);
      4     cout.tie(NULL);
      5     return 0;
      6 };
      7 
      8 class Solution {
      9     static bool check(const unordered_map<string, int> &count, const string &s, int len) {
     10         static unordered_map<string, int> lcount;
     11         lcount.clear();
     12         for (int i = 0; i < s.size(); i += len) {
     13             string word = s.substr(i, len);
     14             const auto it = count.find(word);
     15             if (it == count.end()) return false;
     16             if (++lcount[word] > it->second) return false;
     17         }
     18         return true;
     19     }
     20 
     21   public:
     22     vector<int> findSubstring(const string &s, const vector<string> &words) const {
     23         const int n = words.size(), m = words[0].size();
     24         unordered_map<string, int> count;
     25         for (const string &word : words)
     26             count[word]++;
     27 
     28         vector<int> res;
     29         for (int i = 0; i + m * n <= s.size(); i++) {
     30             if (check(count, s.substr(i, m * n), m)) {
     31                 res.push_back(i);
     32             }
     33         }
     34         return res;
     35     }
     36 };