438. 找到字符串中所有字母异位词

class Solution {
public:
  vector<int> findAnagrams(string s, string p) {
    vector<int> Result;
    unordered_map<char, int> PMap;
    unordered_map<char, int> SMap;

    int L = 0, R = p.length();
    // Initial fill-ins.
    for (char C : p)
      ++PMap[C];
    for (int i = 0; i < R; ++i)
      ++SMap[s[i]];

    while (R <= s.size()) {
      if (PMap == SMap)
        Result.push_back(L);
      if (--SMap[s[L]] == 0)
        SMap.erase(s[L]);
      ++SMap[s[R]];

      ++L;
      ++R;
    }
    return Result;
  }
};

#define I_(x) ((x) - 'a')

class Solution {
public:
  vector<int> findAnagrams(string s, string p) {
    if (s.length() < p.length())
      return {};

    vector<int> Result;
    vector<int> PMap(26);
    vector<int> SMap(26);

    int L = 0, R = p.length();
    // Initial fill-ins.
    for (int i = 0; i < R; ++i) {
      ++PMap[I_(p[i])];
      ++SMap[I_(s[i])];
    }
    if (PMap == SMap)
      Result.push_back(0);

    while (R < s.size()) {
      --SMap[I_(s[L++])];
      ++SMap[I_(s[R++])];

      if (PMap == SMap)
        Result.push_back(L);
    }
    return Result;
  }
};

class Solution {
public:
  vector<int> findAnagrams(string s, string p) {
    if (s.size() < p.size())
      return {};

    vector<int> Result;
    vector<int> SChars(26);
    vector<int> PChars(26);
    for (int i = 0; i < p.size(); ++i) {
      ++PChars[p[i] - 'a'];
      ++SChars[s[i] - 'a'];
    }

    if (SChars == PChars)
      Result.push_back(0);
    for (int i = 0; i < s.size() - p.size(); ++i) {
      --SChars[s[i] - 'a'];
      ++SChars[s[i + p.size()] - 'a'];
      // Putting this statement at beginning end would cause we miss the last
      // window. We can only put it here and add a special case before for-loop.
      if (SChars == PChars)
        Result.push_back(i + 1);
    }
    return Result;
  }
};

class Solution {
public:
  vector<int> findAnagrams(string s, string p) {
    if (s.size() < p.size())
      return {};

    vector<int> Result;
    vector<int> DiffSet(26);
    // Number of different characters between s and p.
    int Diff = 0;
    for (int i = 0; i < p.size(); ++i) {
      // Positive means that patterns have the character while string not;
      // negative vice versa. Keep in mind that the increment/decrement
      // operators are bound to s/p respectively. We'll be using this convention
      // until the program's end.
      ++DiffSet[s[i] - 'a'];
      --DiffSet[p[i] - 'a'];
    }
    // Get the difference.
    for (int D : DiffSet) {
      if (D != 0)
        ++Diff;
    }

    if (!Diff)
      Result.push_back(0);
    for (int i = 0; i < s.size() - p.size(); ++i) {
      // The letter being REMOVED differed from the pattern.
      if (DiffSet[s[i] - 'a'] == 1)
        --Diff;
      // The letter being REMOVED was in the pattern.
      if (DiffSet[s[i] - 'a'] == 0)
        ++Diff;
      // Remove it.
      --DiffSet[s[i] - 'a'];

      // The letter being ADDED will be in the pattern.
      if (DiffSet[s[i + p.size()] - 'a'] == -1)
        --Diff;
      // The letter being ADDED will differ from the pattern.
      if (DiffSet[s[i + p.size()] - 'a'] == 0)
        ++Diff;
      // Add it.
      ++DiffSet[s[i + p.size()] - 'a'];

      if (!Diff)
        Result.push_back(i + 1);
    }
    return Result;
  }
};

class Solution {
public:
  vector<int> findAnagrams(string s, string p) {
    if (p.length() > s.length())
      return {};

    vector<int> Result;

    array<int, 26> pSet;
    pSet.fill(0);
    for (char X : p)
      ++pSet[X - 97];

    array<int, 26> sSet;
    sSet.fill(0);
    for (int i = 0; i < p.length(); ++i)
      ++sSet[s[i] - 97];

    // This one differs from the last one as its window has a fixed length.
    // It actually makes things easier.
    for (int i = 0; i < s.length() - p.length(); ++i) {
      if (sSet == pSet)
        Result.emplace_back(i);

      ++sSet[s[i + p.length()] - 97];
      --sSet[s[i] - 97];
    }

    if (sSet == pSet)
      Result.emplace_back(s.length() - p.length());
    return Result;
  }
};