Day 17 of 31-Day May LeetCode Challenge

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

class Solution {
public:

bool hashEquals(int a[], int b[]){
for(int i=0;i<26;++i) if(a[i]!=b[i]) return false;
return true;
}

vector<int> findAnagrams(string s, string p) {

vector<int> result;
int m = s.size(), n = p.size();
if(m<n) return result;


//method 1 : sliding window + hash
//O(m+n) time & O(n) space, where m is size of string s & n is size of string p
int patt[26] = {0};
for(int i=0;i<n;++i) ++patt[p[i]-'a'];

int text[26] = {0};
for(int i=0;i<n;++i) ++text[s[i]-'a'];
if(hashEquals(patt, text)) result.push_back(0);

for(int i=0;i<m-n;++i){
--text[s[i]-'a'];
if(i+n<m) ++text[s[i+n]-'a'];
if(hashEquals(patt, text)) result.push_back(i+1);
}
return result;
}
};

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Aanchal Patial

Aanchal Patial

13 Followers

We never really grow up, we only learn how to act in public