aboutsummaryrefslogtreecommitdiff
path: root/find_all_anagrams.cpp
blob: 39fe153fdcdfe01a8beda1f10287f9f0f0d68bdb (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 438. Find All Anagrams in a String
#include "leetcode.h"

/*
 * given two strings 's & p', return an array of all the start indices of 'p's
 * anagrams in 's' (any order). an anagram is a word or phrase formed by
 * rearranging the letters of a different word or phrase, typically using all
 * original letters exactly one
 */

class Solution {
public:
  vector<int> findAnagrams(string s, string p) {
    int ssz = s.size(), psz = p.size();
    if (ssz < psz)
      return {};
    vector<int> freq(26, 0), window(26, 0), ans;
    for (int i = 0; i < psz; i++) {
      freq[p[i] - 'a']++;
      window[s[i] - 'a']++;
    }
    if (freq == window)
      ans.push_back(0);
    for (int i = psz; i < ssz; i++) {
      window[s[i - psz] - 'a']--;
      window[s[i] - 'a']++;
      if (freq == window)
        ans.push_back(i - psz + 1);
    }
    return ans;
  }
};

int main() {
  Solution obj;
  for (auto i : obj.findAnagrams("cbaebabacd", "abc"))
    cout << i << ' '; // expect 0 6
  for (auto i : obj.findAnagrams("abab", "ab"))
    cout << i << ' '; // expect 0 1 2
}