leetcode

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

0438.cpp (894B)

      1 class Solution {
      2     typedef unordered_map<char, int> umci;
      3     bool um_eq(const umci &goal, const umci &crnt) {
      4         for (auto [k, v] : goal) {
      5             const auto it = crnt.find(k);
      6             if (it == crnt.end()) return false;
      7             if ((*it).second != v) return false;
      8         }
      9         return true;
     10     }
     11 
     12   public:
     13     vector<int> findAnagrams(string s, string p) {
     14         if (p.size() > s.size()) return {};
     15         unordered_map<char, int> goal, crnt;
     16 
     17         for (int i = 0; i < p.size(); i++) {
     18             goal[p[i]]++;
     19             crnt[s[i]]++;
     20         }
     21 
     22         vector<int> res;
     23         for (int i = p.size(); i < s.size(); i++) {
     24             if (um_eq(goal, crnt)) res.push_back(i - p.size());
     25             crnt[s[i - p.size()]]--;
     26             crnt[s[i]]++;
     27         }
     28         if (um_eq(goal, crnt)) res.push_back(s.size() - p.size());
     29         return res;
     30     }
     31 };